BeakJoon14502_연구소

문제

풀이

우선 문제 자체는 전체 연구소 지도에 벽 3개를 세워 바이러스가 퍼지는 공간을 최소화 하는 문제이다. 언뜻 보기에 쉬워보였지만 생각보다 애를 먹었다. BFS를 이용해서 벽을 세운 뒤의 안전구역을 세는 건 손쉽게 작성했지만 벽을 세우는 부분에서 막혀버렸다. 결국 다른 사람의 코드를 참고하고 나서야 함수를 재귀적으로 활용하면 된다는 걸 깨달았다.

1. 안전구역을 찾는 bfs함수는 기본적인 bfs 방식을 그대로 사용하면 되는데 벽을 새로 세울 때마다 안전구역을 다시 확인해야 하기 때문에 test_lab을 깊은 복사로 복사해야한다.
2. 벽을 세우는 wall함수에서는 벽의 개수를 cnt로 하고 한번 세울 때마다 cnt를 증가시켜가며 wall함수를 재귀호출
3. 함수를 재귀호출 한 뒤 cnt == 3일때 bfs를 호출 하고 break. 이때 모든 경우를 다 확인해야하기 때문에 wall함수 재귀 호출 한 뒤 벽을 세운 부분을 재귀호출 뒤에 다시 0으로 초기화
4. 답 출력

풀이 코드

from collections import deque
import copy

def bfs():
    q = deque()
    test_lab = copy.deepcopy(lab)
    
    for i in range(n):
        for j in range(m):
            if test_lab[i][j] == 2:
                q.append((i,j))
                
    
        while q:
            x, y = q.popleft()
            for i in range(4):
                mx = x + dx[i]
                my = y + dy[i]
                
                if mx < 0 or mx >= n or my < 0 or my >=m:
                    continue
                if test_lab[mx][my] == 0:
                    if test_lab[x][y] == 2:
                        test_lab[mx][my] = 2
                        q.append((mx, my))    
            
    global answer            
    temp = 0  
    for i in test_lab:
        temp += i.count(0)
        
    answer = max(answer, temp)   


def wall(cnt):
    if cnt == 3:
        bfs()
        return
    for i in range(n):
        for j in range(m):
            if lab[i][j] == 0:
                lab[i][j] = 1
                wall(cnt+1)
                lab[i][j] = 0

answer = 0
n,m = map(int,input().split())

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

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

wall(0) 
print(answer)