[BOJ] 2636번: 치즈 - Python

문제

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

문제 풀이

BFS로 구현해보자.

중요한 포인트는 가장자리 치즈를 녹이면서 내부의 치즈에 영향을 주지 않아야한다는 점이다!

알고리즘

for i in range(4):
	nx = x + dx[i]
    ny = y + dy[i]

    if not(0 <= nx < n and 0 <= ny < m):
    	continue
            
    if not cheese[nx][ny] and not visited[nx][ny]:
		q.append([nx, ny])
		visited[nx][ny] = 1
          
	elif cheese[nx][ny] and not visited[nx][ny]:
		cheese[nx][ny] = 0
		visited[nx][ny] = 1
		melt_cnt += 1        

[0,0]부터 탐색하면서 공기를 체크하고, 공기와 접촉하는 치즈를 녹여준다.

아직 방문하지 않은 노드가

1. 공기인 경우, q에 넣고 방문처리 해준다.

2. 치즈인 경우, 치즈를 공기로 바꿔주고 방문처리 해준다.
   내부의 치즈가 연쇄적으로 녹지 않도록 하기 위해 q에 넣지 않는다!!
   방문 처리를 해주었고, q에 넣지 않았기 때문에 해당 치즈가 녹은 시간에는 그 내부의 치즈가 연쇄적으로 녹지 않을 것이다.

소스 코드

import sys
from collections import deque

cheese = []
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def bfs():
    q = deque()
    q.append([0, 0])

    visited = [[0]*m for _ in range(n)]
    visited[0][0] = 1

    melt_cnt = 0  # 요번에 녹은 치즈의 개수
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if not(0 <= nx < n and 0 <= ny < m):
                continue

            # 아직 방문하지 않았고, 공기인 경우
            # q에 넣고 방문처리 해준다.
            if not cheese[nx][ny] and not visited[nx][ny]:
                q.append([nx, ny])
                visited[nx][ny] = 1

            # 아직 방문하지 않았고, 치즈인 경우
            # 치즈를 공기로 바꿔주고 방문처리 해준다.
            # q에 넣지 않으므로써 내부의 치즈가 연쇄적으로 녹지 않도록 한다.
            elif cheese[nx][ny] and not visited[nx][ny]:
                cheese[nx][ny] = 0
                visited[nx][ny] = 1
                melt_cnt += 1

    return melt_cnt


if __name__ == '__main__':
    input = sys.stdin.readline
    n, m = map(int, input().split())

    for _ in range(n):
        cheese.append(list(map(int, input().split())))

    ans = []
    time = 0
    while True:
        cnt = bfs()

        # 더이상 녹은 치즈가 없다면 종료한다.
        if cnt == 0:
            print(time)
            print(ans[-1])
            break
        time += 1
        ans.append(cnt)