[BOJ] 2638 : 치즈

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

2638번: 치즈

문제 유형 : BFS
solved.ac 난이도 : GOLD III
 
문제(자세한 내용은 위 링크(문제 본문) 참조)
N * M의 모눈종이 위에 아주 얇은 치즈가 표시되어있다. N은 세로 격자의 수이고, M은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자의 4변 중에서 최소 2번 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아없어진다. 그러나, 치즈 내부에 있는 공기는 외부 공기와 접촉하지 않아 실내온도의 공기와는 달리 접촉하여도 녹는 데에 영향을 끼치지 않는다. 모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.
 
입력
첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M(5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 있는 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.
 
출력
출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.
 
나의 전략
전체를 탐색하다가, 값이 1인 노드를 찾았을 때, 인접 노드들을 탐색하여, 인접한 공기의 수만큼 치즈의 값을 올리고, 탐색을 마치면 다시 탐색하며 3이 넘는 값을 0으로 바꿔준 뒤, 시간을 진행시키고 다시 처음부터 반복하는 전략을 선정했다.
 
막혔던 부분과 해결
문제를 잘 못 읽어서(...) 외부 공기와 치즈 내부의 공기를 구분하는지 몰랐어서 틀렸다.
[0, 0]부터 너비우선탐색을 통해서 외부 공기만 큐에 넣고, 외부 공기의 값은 -1로 바꿔주는 플랜으로 바꿨다.
문제를 잘 읽자..
 
 
코드(Python)
 

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

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

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

def bfs():
    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]: #외부 공기들을 -1로 칠한다.
                visited[nx][ny] = True
                if graph[nx][ny] == 0:
                    graph[nx][ny] = -1
                    q.append([nx, ny])
    for i in range(n):  #visited 초기화
        for j in range(m):
            visited[i][j] = False
    q.append([0, 0])    #다시 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]:
                visited[nx][ny] = True
                q.append([nx, ny])
                if graph[nx][ny] == 1:
                    for i in range(4):
                        mx = nx + dx[i]
                        my = ny + dy[i]
                        if graph[mx][my] == -1:
                            graph[nx][ny] += 1

while True:
    visited = [[False] * m for _ in range(n)]
    bfs()
    flag = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] >= 3: #외부 공기와 2면 이상 인접한 것들은 없애고,
                graph[i][j] = 0
                flag = 1
            elif graph[i][j] == 2: #하나만 인접한 것들은 다시 1로 바꿔주고,
                graph[i][j] = 1
            elif graph[i][j] == -1: #외부공기들도 초기화해준다.
                graph[i][j] = 0
    if flag == 1: #치즈가 녹은게 있으면 시간을 하나 늘린다
        time += 1
    else:
        break #더 녹이는게 없으면 종료.

print(time)