[백준 14502 연구소] 파이썬 풀이 (골드4)

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

14502번: 연구소

---

문제 요약

• 바이러스는 상하좌우 인접 빈칸으로 퍼져나갈 수 있다.
• 벽 3개를 세워 확산을 최대한 막아야 한다.
• 0=빈칸, 1=벽, 2=바이러스
• 벽을 세운 뒤 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 함. 이 안전영역의 최댓값을 구하라.

---

풀이

먼저 벽을 3개 세우고 나서 바이러스의 위치부터 시작하는 bfs를 수행한다. 이렇게 함으로써 바이러스가 퍼지는 영역을 구해볼 수 있고, 바이러스가 다 퍼지고 난 후의 그래프에서 0의 개수를 세면 안전 영역의 넓이를 구할 수 있다. 이렇게 구한 안전 영역 넓이 중에서 최댓값을 리턴한다.
make_wall은 벽을 세우는 함수이다. 그래프의 각 좌표에 대해 반복하면서 0을 만날 경우 해당 지점을 1로 바꿔준다(즉, 벽을 세운다.) 그 뒤 재귀적으로 벽을 3개까지 세우고, 벽이 3개가 되면 bfs를 수행한다.
bfs는 바이러스의 위치부터 시작해서 바이러스가 도달 가능한 경로를 찾는 함수이다. 일반적인 bfs와 비슷하지만, 첫 출발 지점을 정할 때 그래프에서 2인 지점을 모두 큐에 삽입해놓고 시작한다는 점이 다르다. 그리고 0인 지점을 만나게 되면 해당 지점을 2로 바꿔줌으로써 감염되었다는 것을 표시해준다. (이 덕분에 별도의 visited 배열은 만들어주지 않아도 된다.)

# 백준 14502 연구소 골드4 https://www.acmicpc.net/problem/14502
# 바이러스는 상하좌우 인접 빈칸으로 퍼져나갈 수 있다.
# 벽 3개를 세워 확산을 최대한 막아야 한다.
# 0=빈칸, 1=벽, 2=바이러스
# 벽을 세운 뒤 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 함. 이 안전영역의 최댓값을 구하라.
import sys
input = sys.stdin.readline
from collections import deque
import copy
n, m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))

dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(graph):
    q = deque([])
    # 바이러스의 위치를 모두 큐에 삽입.
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 2:
                q.append((i, j))
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if -1 < nx < n and -1 < ny < m:
                if graph[nx][ny] == 0:
                    graph[nx][ny] = 2 # 감염
                    q.append((nx, ny))

    global answer
    cnt = sum([row.count(0) for row in graph])
    answer = max(answer, cnt)

def make_wall(cnt):
    if cnt == 3:
        # 벽을 3개 세웠으면 bfs 돌기.
        bfs(copy.deepcopy(graph))
        return
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1 # 벽 세우기
                make_wall(cnt+1) # 재귀적으로 벽 세우기
                graph[i][j] = 0 # 벽 원상복구

answer = 0
make_wall(0)
print(answer)