백준 2636: 치즈 - BFS

https://www.acmicpc.net/problem/2636

2636번: 치즈

 

 

(0, 0)를 시작으로 bfs를 돌리면서 0을 만나면 queue에 넣고 가장자리에 있는 치즈를 만나면 0으로 바꾼 뒤 queue에는 넣지 않으면 가장자리에 있는 치즈만 녹이는 것이 가능합니다. (visited는 모두 체크)

 

bfs를 돌면서 가장자리의 치즈를 만나면 count를 해주고 완료 후에는 count를 return해주어 마지막에 모든 치즈가 녹기 전에 몇 개가 있었는지 알 수 있습니다.

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

dy = (-1, 0, 1, 0)
dx = (0, -1, 0, 1)
row, column = map(int, input().split())

def bfs(graph):
    visited = [[False for _ in range(column)] for _ in range(row)]
    queue = deque()
    queue.append((0, 0))
    visited[0][0] = True
    count = 0

    while queue:
        y, x = queue.popleft()
        for ii in range(4):
            ny = y + dy[ii]
            nx = x + dx[ii]
            if not 0<=ny<row or not 0<=nx<column:
                continue
            if visited[ny][nx]:
                continue
            if graph[ny][nx] == '1':
                graph[ny][nx] = '0'
                count += 1
            else:
                queue.append((ny, nx))
            visited[ny][nx] = True

    return count


graph = []
for rr in range(row):
        graph.append(input().split())

day_count = -1
last_cheese_count = 0
while True:
    day_count += 1
    current_cheese_count = bfs(graph)
    if current_cheese_count == 0:
        break
    last_cheese_count = current_cheese_count

print(day_count, last_cheese_count, sep='\n')