[백준] 2636번 : 치즈

2636번: 치즈

해당문제는 치즈가 없어지는 시간을 구하는 문제로 너비우선탐색으로 문제를 해결 할 수 있습니다.

치즈가 녹아서 없어지는 과정은 그래프를 순회하면서 빈공간인 경우 상하 좌우로 치즈를 녹여서 없앱니다.

여기서 상하좌우로 녹인 치즈는 방문처리를하여 다른 빈공간에서 치즈를 또 녹이지 않도록 합니다.

치즈를 녹이기 전 마지막 치즈의 개수는 마지막에 녹인 치즈를 카운팅 하여 모두 녹기전에 있던 치즈의 개수를 알 수 있습니다.

move = [(0,1), (1,0), (0,-1), (-1,0)]
from collections import deque
H,W = map(int, input().split())
table = []

for _ in range(H):
    table.append(list(map(int, input().split())))
def meltcheeze():
    visited = [[False for _ in range(W)] for _ in range(H)] # bfs 방문처리
    cnt = 0 # 녹을 치즈 개수를 샌다.
    queue = deque()
    queue.append((0,0))
    visited[0][0] = True
    while queue:
        i,j = queue.popleft()
        for dy,dx in move:
            ny = dy + i
            nx = dx + j
            if H > ny >= 0 and W > nx >= 0 and not visited[ny][nx]:
                visited[ny][nx] = True
                if table[ny][nx] == 0: # 치즈가 아닐때문 이어서 방문
                    queue.append((ny,nx))

    for i in range(H):
        for j in range(W):
            if table[i][j] and visited[i][j]: # 치즈를 녹인다.
                cnt += 1
                table[i][j] = 0

    return cnt

time = 0
ans = 0
prev = 0
while True:
    ans = meltcheeze()
    if ans == 0:
        break

    time+=1
    prev = ans

print(time)
print(prev)