[백준/BOJ] - 7576번 python 풀이 - BFS

---

key point

 

1. 기본적인 bfs 문제와 다르게 벽을 만드는 함수를 하나 더 생성해야한다.

2. 벽을 만드는 함수는 재귀 함수를 통해 벽을 만들고 bfs 함수에 접근하게 끔 구현한다.

3. 벽을 세우는 매 case마다 기존 배열이 바이러스로 뒤덮이기 때문에 bfs 함수에서 사용되는 메인 배열은 초기 배열 상태이어야 하기에 bfs 접근 할 때 마다 딥카피를 해주어야한다.

4. 바이러스 옮기는 과정을 마무리한 후 배열에 0값을 세어 그 값의 최댓값을 산출해내는 것이 마무리. 

 

알게 된 점

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

 

해당 재귀가 어떤 방식으로 돌아가는지에 대해 감이 안 잡혔으나 디버깅을 통해 어떤 방식으로 진행되는지 감을 잡게되었다. 아래 주석에 디테일한 설명 有

---

import sys
input = sys.stdin.readline
import copy
from collections import deque

n, m =map(int,input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
dx, dy = (-1, 1, 0, 0), (0, 0, -1, 1)
queue = deque()
res = 0
def bfs():
    temp_map = copy.deepcopy(arr)
    for i in range(n):
        for j in range(m):
            if temp_map[i][j] == 2:
                queue.append((i, j))

    while queue:
        a, b = queue.popleft()
        for i in range(4):
            rx = a + dx[i]
            ry = b + dy[i]
            if 0<=rx<n and 0<=ry<m:
                if temp_map[rx][ry] == 0:
                    temp_map[rx][ry] = 2
                    queue.append((rx,ry))
    global res
    count = 0
    for i in range(n):
        for j in range(m):
            if temp_map[i][j] == 0:
                count+=1
    res = max(res, count)

#벽 세우기 함수- 함수가 3번 연속 호출되고 마지막 4번째에 bfs 함수 호출
#bfs가 마무리 되면 return 하여 4번째 함수는 종료되어 3번째 호출된 함수로 이동
#3번째 호출된 함수는 cnt가 2이기 때문에 반복문을 통해 다음 index 위치의 arr에 벽 세우게 된다.
#3번째 호출된 함수가 모든 반복문을 다돌게 되면 2번째 호출된 함수에서 index를 하나 올리게 된다.
#그리고 함수를 한번 더 호출하여 계속 반복하여 벽 세우기를 하는 방식
def makewall(cnt): 
    if cnt == 3:
        bfs()
        return
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 0:
                arr[i][j] = 1
                makewall(cnt+1)
                arr[i][j] = 0


makewall(0)
print(res)