[백준 2638번] 치즈

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

import sys
from collections import deque

input = sys.stdin.readline

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

# 치즈는 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다
# 각 치즈 격자(작은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다

N, M = map(int,input().split())

# 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시
# 모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정

# 출력 : 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간

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

answer = 0

def bfs():
    
    visited = [[False]*M for _ in range(N)]
    count = [[0]*M for _ in range(N)]

    q = deque([(0,0)])
    visited[0][0] = True

    while q:
        cx, cy = q.popleft()

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

            if 0 <= nx < N and 0 <= ny < M:
                if area[nx][ny] == 1:
                    count[nx][ny] += 1
                else:
                    if not visited[nx][ny]:
                        q.append((nx,ny))
                        visited[nx][ny] = True
    for i in range(N):
        for j in range(M):
            if count[i][j] >= 2:
                area[i][j] = 0

def check_empty():
    
    if sum([sum(x) for x in area]) == 0:
        return True
    else:
        return False

while not check_empty():

    answer += 1
    bfs()

print(answer)

 

이번 문제는 N x M 크기의 공간에 치즈가 존재하고, 해당 치즈는 공기(빈 공간)을 2개 이상 접촉하면 1시간만에 녹는다고 가정했을 때 모든 치즈가 녹는데까지 걸리는 시간을 구하는 문제이다.

 

이전에 풀어봤던 유형이라 금방 풀이법을 떠올릴 수 있었는데, 해당 문제를 풀기 위해서는 2가지 함수를 구현해야 한다.

1. 맞닿는 공기의 개수를 Counting 해주는 함수(DFS/BFS 알고리즘 활용)
2. 모든 치즈가 녹았는지 확인하는 함수

"모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다" 라는 조건이 존재하기 때문에 가장자리에 있는 아무 자리에서 탐색을 시작해도 맞닿는 공기의 개수를 구할 수 있다. 그래프 탐색 연습해볼 수 있었던 문제였다 :)