[백준][BFS] - 14502. 연구소

from collections import deque
import copy


def BFS():
    q = deque()
    tmp = copy.deepcopy(graph)
    for i in range(n):
        for j in range(m):
            if tmp[i][j] == 2:
                q.append((i,j))
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            if 0<=nx<n and 0<=ny<m and tmp[nx][ny] == 0:
                tmp[nx][ny] = 2
                q.append((nx,ny))
    global res
    cnt = 0
    for i in range(n):
        cnt += tmp[i].count(0)
    #해당 벽이 세워지는 경우마다 0의 갯수가 가장 많은 경우를 res로 넣어준다.
    res = max(res, cnt)
    

def wall(cnt):
    #해당 벽이 3개 세워졌다면 BFS  실행
    if cnt == 3:
        BFS()
        return
    
    #cnt == 3일 땐 for문 작동 X
    for i in range(n):
        for j in range(m):
           if graph[i][j] == 0:
               graph[i][j] = 1
               wall(cnt+1)
               #해당 구역을 1로 만든 뒤 바이러스 갯수를 다 세고 나서 다시 0으로 만들어주어야 다음 확인이 가능
               graph[i][j] = 0
 

if __name__ =="__main__":
    n, m = map(int,input().split())
    graph = [list(map(int,input().split())) for _ in range(n)]
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]
    res = 0
    wall(0)
    print(res)

• 3가지의 챕터(?)를 생각해서 짜야한다.
  1. 그래프의 아무 것도 없느 지점(=0인 구간)에 벽(1)을 3개 놓는 것
  2. 벽을 3개 놓았다면 이제 안전 지역이 몇개인지를 구해야 하는데 이때는 바이러스가 어디까지 퍼질 수 있는지를 구해야 한다
  3. 그리고 바이러스가 다 퍼졌다면 안전구역의 갯수를 구해 벽을 3개 세운 곳에 안전 구역이 제일 많은 곳을 비교해 더 많은 곳을 답으로 넣어줄 수 있도록 진행해야 한다.
• wall(cnt)는 재귀를 사용해서 모든 벽을 놓을 수 있는 구역에 벽을 놓아 벽이 3개가 놓아졌다면 해당 구역에 바이러스가 퍼지지 않은 안전구역이 몇개인지를 확인해야 한다.
  • 이때는 2중 for 문을 돌면서 해당 부분에 모두 벽을 설치할 수 있게 한다.
• 구역을 확인 한 후 다시 다음 확인에 지장이 없도록 0으로 만들어주어야 한다.

해당 문제는 BFS와 재귀의 개념을 안다면 쉽게 풀 수 있는 문제이다.