백준 2636번 : 치즈

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

2636번: 치즈

 

고민하다가 자체적으로 난이도를 높혀버린 문제이다.

 

 문제 풀이 자체는 다른 그래프 알고리즘과 크게 다르지 않다. 문제를 간단히 요약하자면, 1x1 크기의 정사각형으로 이루어진 판 위에 치즈가 일부분 올려져있고 이 치즈는 공기에 노출된 상태에서 1시간이 지나면 녹아 없어진다. 치즈엔 구멍이 뚫려 있는데 다행히도 이 구멍엔 공기가 없어서 치즈 안쪽에서부터 녹아 없어지진 않지만, 바깥 공기가 구멍 안쪽으로 들어갈 수 있는 틈이 벌어진 경우 공기가 들어가서 치즈가 녹을 수 있다. 치즈가 전부 없어지는데 걸리는 시간과 마지막까지 남아있던 치즈가 놓여있던 칸의 개수를 구하는 문제다.

 

 해결 아이디어는 다음과 같다. 치즈가 놓여져있지 않은 칸은 공기(치즈 바깥 공간) 혹은 구멍(치즈 안쪽 공간)으로 분류된다. 치즈를 녹일 수 있는 건 공기이기 때문에 공기를 찾아서 BFS 탐색을 진행하고, 탐색을 진행하던 도중 인접 칸에 치즈가 있는 곳에 방문하면 그 치즈를 녹인다. 이 과정을 치즈가 모두 없어질 때 까지 반복하면 된다.

 

 위 아이디어를 떠올리는데 걸리는 시간은 길지 않았다. 나는 이전에 이와 비슷해보이는 문제(백준 5545번:일루미네이션)를 풀었었다. 그래서 나는 고민하지않고 바로 공기와 치즈 구멍을 구분하는 알고리즘을 생각하기 시작했다. 왜냐하면 공기와 구멍은 값이 0으로 동일한데, 치즈를 녹일 수 있는 것은 공기만 가능하기 때문이다. 5545번도 그렇고, 공기와 구멍을 구분해낼 수 있느냐 없느냐가 문제 해결에 있어서 가장 중요한 핵심이라고 생각했다. 하지만 이 과정이 필요하지 않다는 걸 깨닫게 된 건 문제를 풀고 나서였다.(여기서만 1시간 가량이 걸렸다.)

 

 결론적으로, 공기와 구멍을 구분할 필요가 없다. 그 이유는 판의 가장 바깥쪽은 항상 공기이기 때문이다. 만약 공기가 있는 곳이 어딘지 모른다면, 선형 탐색을 통해 판의 모든 칸들을 확인하고 공기인지 아닌지를 판별해야한다. 하지만 공기가 있는 칸을 알 수만 있다면 BFS 탐색을 통해 인접한 곳에 있는 공기들을 찾을 수 있고 그 과정에서 치즈와 닿는 공기 역시 찾을 수 있기 때문이다.

 

이전에 풀었던 문제와 비슷해 보인다고해서 똑같이 접근한 것이 문제를 더 어렵게 만들어버렸다.

항상 문제를 정확하게 읽어야 한다는걸 이번에 또 다시 배웠다.

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

def bfs(p):
    dx, dy = [1,0,-1,0], [0,1,0,-1]
    v = [[False] * m for _ in range(n)]
    cnt = 0
    queue = deque([(0,0)])
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            px, py = x+dx[i], y+dy[i]
            if px < 0 or px > n-1 or py < 0 or py > m-1:
                continue
            if not v[px][py]:
                v[px][py] = True
                if p[px][py] == 0:
                    queue.append((px, py))
                else:
                    p[px][py] = 0
                    cnt += 1
    return cnt

n, m = map(int, input().split())
plate = [list(map(int, input().split())) for _ in range(n)]
cnt, hour, result = 0, 0, 0

for i in plate:
    cnt += i.count(1)

while cnt > 0:
    result = cnt
    cnt -= bfs(plate)
    hour += 1
print(hour, result, sep='\n')