[백준 2636번] 치즈

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

 

# 판의 가장자리에는 치즈가 놓여 있지 않다.
# 치즈에는 하나 이상의 구멍이 있을 수 있다.
# 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다.
# 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다.

# 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램

from collections import deque

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

r, c = map(int,input().split())

area = [list(map(int,input().split())) for _ in range(r)]

melt_count_list = []

time = 0

def melt():
    
    queue = deque([(0,0)])

    melt_list = []

    while queue:
        
        x, y = queue.popleft()

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

            if 0 <= nx < r and 0 <= ny < c and not visited[nx][ny]:
                if area[nx][ny] == 1:
                    melt_list.append((nx,ny))
                elif area[nx][ny] == 0:
                    queue.append((nx,ny))

                visited[nx][ny] = True

    for mx, my in melt_list:
        area[mx][my] = 0

    melt_count_list.append(len(melt_list))

    return len(melt_list)
    
while True:
    
    visited = [[False]*c for _ in range(r)]

    count = melt()

    if count == 0:
        print(time)
        print(melt_count_list[-2])
        break

    time += 1

 

이번 문제는 직사각형 모양의 판에 있는 치즈가 있고, 치즈 중 공기와 맞닿아있는 부분이 1시간마다 녹는다고 가정했을 때 '공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간'과 '모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수'를 구하는 문제이다.

 

이 문제를 풀기 위해서는 치즈를 둘러싸고 있는, 즉 공기가 있는 공간만 구할 수 있으면 되는데, 처음에 이 문제를 접근할 땐 판의 가장자리를 무시하고 풀이하려고 하다보니 '공기가 있는 공간'과 '공기가 없는 공간'을 어떻게 구분지어야 할지 고민하느라 시간을 많이 보냈다.

 

하지만 이렇게 풀이하는건 상당히 복잡하고, 다른 사람의 풀이를 참고해본 결과 정말 간단하게 풀이하는 방법이 존재했다.

 

바로 판의 가장자리에 존재하는 좌표에서부터 BFS 알고리즘을 실행(가장자리의 좌표는 모든 공간과 0으로 연결되어 있으므로 모든 치즈를 둘러쌀 수 있음)하여 공기랑 맞닿아있는 바깥쪽 치즈를 녹이는 것이다.

 

배운 점 및 느낀 점

1. BFS를 항상 특정 좌표 (x, y)에서만 시작하려고 하지말자.
2. 문제에서 궁극적으로 구하고자 하는 값이 무엇인지 정확하게 파악하자.