BFS/DFS_연구소 풀이 암기

* 완전탐색 -> BFS/DFS 활용 (반복문, 재귀함수) [모든 경우의 수 다 계산해야 하므로]

 

모든 조합을 계산할 때 :

1) 파이썬 조합 라이브러리 활용 (from itertools import combinations)

2) BFS/DFS 이용 (* DFS -> 벽을 세웠을 경우, 끝까지 탐색하여 전체 총량을 확인해야하므로 (깊이 우선 탐색) )

 

힌트: 

1) DFS 이용해 울타리 설치하면서, 매번 안전영역의 크기 계산

   (1) 울타리가 3개 설치된 경우

   (2) 각 바이러스의 위치에서 전파 진행(virus)

   (3) 안전영역의 최댓값 계산

   (4) 빈 공간에 울타리 설치 **암기 "dfs(count)의 의미는 무엇인가?"

어려운 포인트) dfs(count)는 모든 영역을 다 점검하여, 어디에 울타리를 설치할지 매번 목표치와 확인하여 결과치를 정하는 것

# "dfs(count)의 의미는 무엇인가?"

def dfs(count): # DFS활용해서 울타리 설치하면서, 매번 안전 영역의 크기 계산
    global result # 지역변수를 전역변수로 확장시키기 #get_socre() 활용
    # 울타리가 3개 설치된 경우
    if count == 3:
        for i in range(n):
            for j in range(m):
                temp[i][j] = data[i][j] # 매번 안전영역의 크기를 계산(목표치)
        # 각 바이러스의 위치에서 전파 진행
        for i in range(n):
            for j in range(m):
                if temp[i][j] == 2:
                    virus(i, j)
        # 안전 영역의 최대값 계산
        result = max(result, get_score())
        return
        
    # 빈 공간에 울타리를 설치
    for i in range(n):
        for j in range(m):
            if data[i][j] == 0:
                data[i][j] = 1 # 일단 울타리(벽)을 설치해보기
                count += 1
                dfs(count) # 안전영역의 최댓값 계산해보기(result)
                data[i][j] = 0 # 안전영역 목표치와 같지 않으면, 울타리(벽) 해제하기
                count -= 1
dfs(0)

문제풀이

n, m = map(int, input().split())
data = [] # 초기 맵 리스트
temp = [[0] * m for _ in range(n)] # 벽을 설치한 뒤의 맵 리스트

for _ in range(n):
    data.append(list(map(int, input().split())))

# 4가지 이동 방향에 대한 리스트
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

result = 0

# 깊이 우선 탐색(DFS)을 이용해 각 바이러스가 사방으로 퍼지도록 하기
def virus(x, y):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 상, 하, 좌, 우 중에서 바이러스가 퍼질 수 있는 경우
        if nx >= 0 and nx < n and ny >= 0 and ny < m:
            if temp[nx][ny] == 0:
                # 해당 위치에 바이러스 배치하고, 다시 재귀적으로 수행
                temp[nx][ny] = 2
                virus(nx, ny)

# 현재 맵에서 안전 영역의 크기 계산하는 메서드
def get_score():
    score = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                score += 1
    return score

# 깊이 우선 탐색(DFS)을 이용해 울타리를 설치하면서, 매 번 안전 영역의 크기 계산
def dfs(count):
    global result
    # 울타리가 3개 설치된 경우
    if count == 3:
        for i in range(n):
            for j in range(m):
                temp[i][j] = data[i][j]
        # 각 바이러스의 위치에서 전파 진행
        for i in range(n):
            for j in range(m):
                if temp[i][j] == 2:
                    virus(i, j)
        # 안전 영역의 최대값 계산
        result = max(result, get_score())
        return
    # 빈 공간에 울타리를 설치
    for i in range(n):
        for j in range(m):
            if data[i][j] == 0:
                data[i][j] = 1
                count += 1
                dfs(count)
                data[i][j] = 0
                count -= 1

dfs(0)
print(result)

분석하기

1) 초기 설정

n, m = map(int, input().split())
data = [] # 초기 맵 리스트
temp = [[0] * m for _ in range(n)] # 벽을 설치한 뒤의 맵 리스트

for _ in range(n):
    data.append(list(map(int, input().split())))

2) BFS/DFS 정형적인 문제풀이 (암기 필요) 

# 4가지 이동 방향에 대한 리스트
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

result = 0

# 깊이 우선 탐색(DFS)을 이용해 각 바이러스가 사방으로 퍼지도록 하기
def virus(x, y):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 상, 하, 좌, 우 중에서 바이러스가 퍼질 수 있는 경우
        if nx >= 0 and nx < n and ny >= 0 and ny < m:
            if temp[nx][ny] == 0:
                # 해당 위치에 바이러스 배치하고, 다시 재귀적으로 수행
                temp[nx][ny] = 2
                virus(nx, ny)

3) 현재 맵에서 안전 영역의 크기 계산하는 메서드

def get_score():
    score = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                score += 1
    return score

4) 깊이 우선 탐색(DFS)을 이용해 울타리를 설치하면서, 매 번 안전 영역의 크기 계산

def dfs(count): #DFS활용해서 울타리 설치하면서, 매번 안전 영역의 크기 계산
    global result #지역변수를 전역변수로 확장시키기 #get_socre() 활용
    # 울타리가 3개 설치된 경우
    if count == 3:
        for i in range(n):
            for j in range(m):
                temp[i][j] = data[i][j] #매번 안전영역의 크기를 계산(목표치)
        # 각 바이러스의 위치에서 전파 진행
        for i in range(n):
            for j in range(m):
                if temp[i][j] == 2:
                    virus(i, j)
        # 안전 영역의 최대값 계산
        result = max(result, get_score())
        return
    # 빈 공간에 울타리를 설치
    for i in range(n):
        for j in range(m):
            if data[i][j] == 0:
                data[i][j] = 1 #일단 울타리(벽)을 설치해보기
                count += 1
                dfs(count) #안전영역의 최댓값 계산해보기(result)
                data[i][j] = 0 #안전영역 목표치와 같지 않으면, 울타리(벽) 해제하기
                count -= 1

dfs(0)
print(result)