[Python/파이썬] 백준 2638번 - 치즈

문제 설명

입력과 출력 및 예제

---

풀이 코드

2차원 배열의 값들을 하나씩 탐색해 해당 부분이 외부 공기와 2번 이상 접촉했는지 확인해야 하므로 BFS를 이용해 문제를 풀 수 있다.

내 코드에서 주의할점으로는 치즈가 있는 부분은 visited 방문 처리 하지 않았다는 점인데 여러 면에서 공기와 접촉이 될 수 도 있기 때문에

이 부분을 방문 처리 해버리게 되면 해당 치즈는 무조건 한 면만 접촉되는 것이 되기 때문이다.

나머지 부분은 주석을 통해 이해할 수 있을 것으로 생각되어 자세한 설명은 생략한다.

 

정답 코드

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

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

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

# 외부 공기와 접촉하는 부분 탐색
def bfs():
    visited = [[False] * m for _ in range(n)]
    q = deque()
    q.append((0, 0))
    visited[0][0] = True

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                if cheeze[nx][ny] >= 1: 
                    cheeze[nx][ny] += 1
                else:
                    q.append((nx, ny))
                    visited[nx][ny] = True

# 외부 공기와 2변 이상 접촉한 부분을 제거
def melt_cheeze():
    melted = 0
    for i in range(n):
        for j in range(m):
            if cheeze[i][j] >= 3:
                cheeze[i][j] = 0
                melted += 1
            elif cheeze[i][j] >= 2:
                cheeze[i][j] = 1
    return melted

time = 0
while True:
    bfs()
    melted = melt_cheeze()
    
    if melted:
        time += 1
    else: # 더 이상 녹일 부분이 없다면 시간 반환
        print(time)
        break