[백준 - Python] 14502. 연구소 (DFS/BFS)

https://www.acmicpc.net/problem/14502

14502번: 연구소

 

코드

from collections import deque
import copy
n, m = map(int, input().split())
graph = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs():
    queue = deque()
    tmp_graph = copy.deepcopy(graph)

    for i in range(n):
        for j in range(m):
            if tmp_graph[i][j] == 2:
                queue.append((i, j))

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if tmp_graph[nx][ny] == 0:
                    tmp_graph[nx][ny] = 2
                    queue.append((nx, ny))

    global answer
    cnt = 0

    for i in range(n):
        cnt += tmp_graph[i].count(0)

    answer = max(answer, cnt)


def makeWall(cnt):
    # 벽 3개가 세워지면 바이러스 퍼뜨리기
    if cnt == 3:
        bfs()
        return

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                makeWall(cnt+1)
                graph[i][j] = 0  # 벽을 다시 허무는 과정 (백 트래킹)

for i in range(n):
    graph.append(list(map(int, input().split())))

answer = 0
makeWall(0)
print(answer)

 

이 문제의 핵심이 되는 부분은

"벽을 어떤 기준으로 세워야 안전 구역의 넓이가 최대가 되는가" 이다.

 

문제에서 벽 3개를 반드시 세워야 한다고 했기 때문에

별 수 없이 벽을 세울 수 있는 모든 경우의 수를 탐색해야 하는데,

효율적인 탐색을 위해 백트래킹 방식을 사용하는 것이 좋다.

 

백트래킹은 쉽게 말하면,

후보군에서 제약 조건을 점진적으로 체크하다가,

해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시

다시는 이 후보군을 체크하지 않겠다는 표시(backtrack)를 하고

다른 후보군으로 넘어가 최적의 해를 효율적으로 찾는 방식이다.

 

백트래킹에 관한 개념은

다른 글에서 상세하게 정리해 다뤄야겠다.

 

makeWall 함수는 벽을 세우는 함수로

벽이 세워질 수 있는 모든 경우의 수를 살펴보며

벽이 3개 세워졌을 때,

bfs로 탐색을 시작한다.

 

bfs 함수 내에서는 바이러스가 퍼져나가는 과정과

바이러스가 다 퍼졌을 때 존재하는 안전구역의 최대 넒이를 구해서 answer에 저장한다.

 

이 때, 최종 결과를 저장하는 answer 변수를 전역으로 선언하여

어떤 좌표 조합으로 3개의 벽이 세워져서 bfs가 수행이 된 것이든지 간에

현재 0의 개수, 즉 안전구역의 최댓값과 이전의 bfs 함수에서 계산된

answer값이 비교될 수 있도록 하였다.

 

graph[i][j] = 0 이라는 백트래킹 코드를 사용하였는데,

결국 전체 경우의 수를 탐색해

안전 구역의 최댓값들 중에서 최댓값을 구하기 위한 코드이고

효율적인 탐색을 위한 백트래킹 코드는 아닌 것 같다.