[BOJ] 2638 치즈 바로가기
📍 문제
N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.
<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.
모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.
📍 입력
첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.
📍 출력
출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.
📍 풀이
🧷 풀이 과정
치즈 문제의 가장 중요한 포인트는 외부 공기와 내부 공기를 구분하는 방법이다.
방법은 BFS 를 이용하여 외부 공기를 탐색하는 방법을 사용하는 것이다.
아래의 예제를 통해 외부 공기를 탐색하는 방법과 외부 공기와 맞닿은 치즈의 변화값에 대하여 쉬운 이해를 돕기 위해 그림을 통해 설명해보겠다.
치즈는 노랑색, 외부 공기는 하늘색으로 표현하면 위와 같다.
외부 공기는 (0, 0) 에서부터 시작해서 BFS 방식으로 퍼져 나간다.
외부 공기가 퍼져나가는 중 치즈와 만나는 지점에서 탐색을 종료하고 치즈에 해당하는 위치의 값을 1 증가시킨다.
BFS 연산이 종료된 후의 결과는 아래와 같다.
해당 상태를 보면 치즈의 값이 3 이상인 경우는 외부 공기와 2번 이상 맞닿은 경우이고, 2 인 경우는 외부 공기와 1번 맞닿은 경우이고, 1 인 경우 외부 공기와 한번도 맞닿지 않은 경우이다.
해당 결과를 통해 치즈의 값이 3 이상인 경우의 치즈를 제거하고 나머지 치즈는 다시 1 의 값으로 갱신한다.
모눈 종이 위의 모든 치즈가 녹아 없어질 때까지 BFS 탐색 및 치즈 제거 연산을 반복한다.
✍ 코드
# BOJ 2638 치즈
# https://www.acmicpc.net/problem/2638
from sys import stdin
from collections import deque
def solution(N, M, graph):
answer = 0
def bfs():
visited = [[False] * M for _ in range(N)]
visited[0][0] = True
queue = deque([(0, 0)])
while queue:
x, y = queue.popleft()
for dx, dy in ((1,0), (0,1), (-1,0), (0,-1)):
nx, ny = x + dx, y + dy
if (0 <= nx < M) and (0 <= ny < N) and not visited[ny][nx]:
# 외부 공기와 맞닿은 치즈인 경우
if graph[ny][nx] >= 1:
# 해당 치즈 가중치 + 1
graph[ny][nx] += 1
# 외부 공기와 맞닿은 외부 공기일 경우
else:
# 해당 공기 위치 추가
queue.append((nx, ny))
visited[ny][nx] = True
while True:
bfs() #
flag = True
for y in range(N):
for x in range(M):
# 2변 이상이 외부공기와 맞닿은 경우
if graph[y][x] >= 3:
# 치즈 제거
graph[y][x] = 0
flag = False
# 1변만 외부공기와 맞닿은 경우
elif graph[y][x] == 2:
# 치즈 상태 복구
graph[y][x] = 1
flag = False
if flag: break
answer += 1
return answer
# input
N, M = map(int,stdin.readline().split())
graph = [list(map(int,stdin.readline().split())) for _ in range(N)]
# res
res = solution(N, M, graph)
print(res)