https://www.acmicpc.net/problem/2638
접근
- bfs 탐색해서 공기와 접촉한 치즈를 찾는다. 탐색된 공기, 치즈는 방문 처리해서 중복 탐색을 방지한다.
- 공기와 접촉한 치즈 중 두 변 이상이 접촉한 치즈를 필터링한다.
- 필터링되지 않은 치즈는 다시 bfs 탐색하기 위해 방문 처리를 해제한다.
- 필터링된 치즈를 녹인다.
- 녹인 치즈부터 bfs 탐색하여 치즈가 없어질 때까지 반복한다.
풀이
from sys import stdin
from collections import deque
def bfs(q):
cheese = []
while q:
x, y = q.popleft()
for i in range(4):
nx = x + directions[i]
ny = y + directions[3 - i]
if is_out_of_range(nx, ny) or visited[nx][ny]:
continue
visited[nx][ny] = True
if board[nx][ny]: # (1)
cheese.append((nx, ny))
else:
q.append((nx, ny))
return cheese
def is_out_of_range(x, y):
return x < 0 or x >= n or y < 0 or y >= m
def melt(cheese):
melting_cheese = []
for x, y in cheese:
cnt = 0
for i in range(4):
nx = x + directions[i]
ny = y + directions[3 - i]
if is_out_of_range(nx, ny) or not visited[nx][ny] or board[nx][ny]: # (2)
continue
cnt += 1
if cnt >= 2:
melting_cheese.append((x, y))
else:
visited[x][y] = False
for x, y in melting_cheese: # (3)
board[x][y] = 0
return melting_cheese
n, m = map(int, stdin.readline().split())
board = [[*map(int, stdin.readline().split())] for _ in range(n)]
visited = [[False] * m for _ in range(n)]
directions = [1, 0, -1, 0]
hours = 0
q = deque([(0, 0)])
while True:
cheese = bfs(q)
if not cheese:
break
melting_cheese = melt(cheese)
q = deque(melting_cheese) # (4)
hours += 1
print(hours)
- (1) 치즈는 치즈 리스트에 저장하고 외부 공기만 다시 큐에 넣어서 표면의 치즈만 탐색하도록 한다.
- (2) 치즈의 상하좌우를 확인할 때 외부 공기만 카운트되어야 한다. 방문 처리되지 않은 것은 내부 공기 또는 공기와 접촉하지 않은 치즈이고, 방문했지만 치즈인 것은 공기와 접촉한 다른 치즈이다.
- (3) 녹일 치즈를 찾고 바로 녹이면 공기와 한 변만 접촉해 있던 다른 치즈가 녹을 수 있다. 따라서 녹일 치즈들을 리스트에 저장하고 한 번에 녹인다.
- (4) 이미 탐색한 외부 공기는 방문 처리했기 때문에 녹인 치즈부터 bfs 탐색해서 탐색 범위를 좁힌다.