[백준] 14502번 연구소 - Python

이번에 해결해 볼 문제는 백준에 있는 연구소이다.

---

문제 설명

• 크기 N x M의 연구소가 있다.
• 0은 빈칸, 1은 벽, 2는 바이러스가 있는 곳을 나타낸다.
• 바이러스는 상하좌우로 인접한 빈칸으로 계속해서 퍼져나갈 수 있다.
• 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.
• 새로운 벽을 세운 연구소에서 바이러스가 퍼져나갔을 때 빈칸의 개수를 출력하면 된다.

문제 아이디어

• 연구소의 크기가 가장 큰 경우 8 x 8이므로 3개의 벽을 세울 수 있는 모든 경우의 수에 대하여 바이러스가 퍼졌을 때의 빈칸의 개수를 계산하면 된다.
• 벽을 세우는 경우의 수를 계산하기 위해 깊이우선탐색을 수행하고 바이러스가 퍼지는 경우를 계산하기 위해 넓이우선탐색을 수행한다.

문제 해결 코드

import sys
from copy import deepcopy
from collections import deque

input = sys.stdin.readline
N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]

# virus가 표시된 위치 저장
virus = []
for i in range(N):
    for j in range(M):
        if graph[i][j] == 2:
            virus.append((i,j))

answer = 0

# virus가 연구소에 퍼지도록 함
def bfs(arr, v):
    while v:
        i, j = v.popleft()
        for di, dj in [(1,0),(-1,0),(0,1),(0,-1)]:
            new_i, new_j = i + di, j + dj
            if 0 <= new_i < N and 0 <= new_j < M:
                if arr[new_i][new_j] == 0:
                    v.append((new_i, new_j))
                    arr[new_i][new_j] = 2
    return arr

# 빈칸의 개수 찾기
def safe(arr):
    cnt = 0
    for i in range(N):
        for j in range(M):
            if arr[i][j] == 0:
                cnt += 1
    return cnt

# 빈칸에 벽을 세우기 위해 가능한 경우
def dfs(x):
    global answer

    if len(visited) == 3:
        # 기존 그래프를 유지하기위해 deep copy
        copy_graph = deepcopy(graph)
        # 벽을 세우기로 한 위치에 벽 세우기
        for i, j in visited:
            copy_graph[i][j] = 1
        answer = max(answer, safe(bfs(copy_graph, deque(virus))))
        return

    for i in range(x, N*M):
        r, c = divmod(i, M)

        # 빈칸이면서 아직 방문하지 않은 경우 -> 중복을 허용하지 않는 조합과 같다.
        if graph[r][c] == 0 and not (r, c) in visited:
            visited.append((r,c))
            dfs(i)
            visited.pop()

for i in range(N*M):
    r, c = divmod(i, M)

    # 빈칸인 경우
    if graph[r][c] == 0:
        visited = [(r, c)]
        dfs(i)

print(answer)

간단한 예시