[Python] 백준 2636번: 치즈 - bfs

문제

2636번: 치즈

풀이

가장자리인지를 어떻게 판단해야하나 고민했는데,

결론은 [0,0]부터 bfs로 돌면서 상하좌우 탐색을 하고 

0을 만나면 큐에 넣기, 1을 만나면 큐에 안넣고 가장자리라고 표시를 해주면 된다.

0(공기)에서 만난 1(치즈)는 늘 가장자리일수밖에 없기 때문!

 

치즈 가장자리를 만나면 1을 2로 바꿔줬고, 큐가 다 비면 한시간이 지났다고 판단해 2를 모두 0으로 바꿔줬다. 

탐색할때는 visited배열을 둬서 똑같은 곳은 방문하지 않도록 관리했다.

 

 

import sys
from collections import deque

# 위 - 오 - 아래 - 왼 순서
dr = [1, 0, -1, 0]
dc = [0, 1, 0, -1]

H, W = map(int, sys.stdin.readline().split(" "))
field = []

for _ in range(H):
    field.append(list(map(int, sys.stdin.readline().split(" "))))

left = 0
for i in range(H):
    for j in range(W):
        if field[i][j] == 1:
            left += 1

def bfs(left):
    while queue:
        now = queue.popleft()

        for i in range(4):
            ndr = now[0] + dr[i]
            ndc = now[1] + dc[i]

            if 0 <= ndr < H and 0 <= ndc < W and visited[ndr][ndc] == 0:
                visited[ndr][ndc] = 1

                # 치즈 가장자리를 만나면
                if field[ndr][ndc] == 1:
                    field[ndr][ndc] = 2
                    left -= 1
                else:
                    queue.append([ndr, ndc])

    return left


def delete():
    for i in range(H):
        for j in range(W):
            if field[i][j] == 2:
                field[i][j] = 0

queue = deque()

count = 0
temp = left
while left != 0:
    visited = [[0 for _ in range(W)] for _ in range(H)]
    queue.append([0, 0])
    visited[0][0] = 1
    left = bfs(left)

    if left != 0:
        temp = left

    count += 1
    delete()

print(count)
print(temp)