[백준] 2636번, 치즈 (Python)

문제

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

2636번: 치즈

 

코드

import collections

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

def bfs():
    queue = collections.deque()
    queue.append((0,0))
    check = [[False] * m for _ in range(n)]
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    count = 0
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == 0 and check[nx][ny] == False:
                    check[nx][ny] = True
                    queue.append((nx,ny))
                # (0,0) 에서 시작해서 처음 만나는 1들은 모두 가장자리이다.
                elif graph[nx][ny] == 1:
                    # queue에 추가해주는게 아니라 0으로 바꿔줘 녹게만들어준다.
                    graph[nx][ny] = 0
                    count += 1
                    check[nx][ny] = True
    return count

result = []
time = 0
while True:
    count = bfs()
    result.append(count)
    # count가 0이면 모든 치즈가 녹았다는 소리이다.
    if count == 0:
        break
    time += 1

print(time)
# 한시간 전에(모두 녹기전 단계) count를 출력해야 되므로 [-2]를 출력한다.
print(result[-2])

치즈가 1로 주어지는데 가장 자리 치즈들이 먼저 녹기 시작하고 몇 시간만에 모두 녹게 되는지랑 모두 녹기 한시간전에 몇개의 치즈가 남았는지 출력하는 문제이다.

 

가장자리 치즈인지 판단하는게 가장 키포인트인 문제였다..

 

행렬이 주어졌을때 가장 바깥쪽은 치즈가 놓일수 없으므로 항상 (0,0)부터 시작해 상하좌우로 확인을 하는데 처음 1이 나오는 곳들이 가장자리이다.

그래서 1을 발견하면 0으로 만들어 녹게해주고 queue에 넣지않는다.(한번 실행할때 가장자리 치즈만 없애주므로 계속 queue에 넣어줄 필요가 없다.)

 

치즈가 모두 녹을때까지 무한루프를 돌아 얼마큼에 시간이 걸렸는지랑 모두 녹기 한시간전에 값을 출력해주면된다.