🟩 [백준] [Python] [Gold3] 2638번_치즈

문제

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

2638번: 치즈

풀이

# 백준 2638번 문제 - 치즈
from collections import deque
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
dx, dy = [0,0,-1,1],[1,-1,0,0]

def bfs():
    q = deque()
    visited = [[0]*m for _ in range(n)]
    q.append((0,0))
    visited[0][0] = 1
    
    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:
                if graph[nx][ny] == 0 and not visited[nx][ny]:
                    q.append((nx, ny))
                    visited[nx][ny] = 1
                elif graph[nx][ny] == 1:
                    visited[nx][ny] += 1
    melted = []
    for i in range(n):
        for j in range(m):
            if visited[i][j] >= 2:
                melted.append((i,j))
    return melted

answer = 0
while True:
    melted = bfs()
    if not melted:
        break
    answer += 1
    for x, y in melted:
        graph[x][y] = 0
print(answer)

BFS 문제라는 것은 바로 알았는데 내부 치즈를 해결하는데 오래 생각을 했다. 

치즈가 녹는 조건은 외부 공기 2번이상 접촉하는 것인데 모두 탐색하면서 visited 가 2번 이상 방문했다면 치즈가 녹는 것이다.