문제 풀이 과정
"외곽"을 치즈에서 직접 정의하기는 어렵습니다. 내부 공기를 명백하게 정의하는 폐곡선을 찾는 그런 어려운 방법은 효율적일거 같지 않고.. 쉬운 방법이 있을거 같습니다. 공기의 차이를 어떻게 구분해야 할까요..?
문제에, 단서가 주어져 있습니다.
모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다.
네, 4개의 구석은 문제가 없겠군요. 4개의 구석은 안전하게 바깥 공기라고 확신할 수 있겠습니다.! 거기와 연결된 공기는 모두 외부 공기, 따로 치즈에 갇힌 공기는 접근이 불가능하니 내부 공기네요. 이제 해결이 가능하겠네요.!
푸는 순서는 다음과 같습니다.
1 / 현재 시점의 모든 바깥 공기를 찾습니다. 연결된 부분만 찾으면 되므로 BFS로 해결이 되네요.
2 / 현재 존재하는 모든 치즈에 대해서, 바깥 공기와 두개 이상 맞닿아 있는지 확인합니다. 내부 공기와 맞닿아 있어도 바깥과 두개 이상 닿아 있으면 치즈는 녹습니다.
3 / 바깥과 닿아 있기에, 녹게 되는 치즈 자리는 추후 바깥 공기로 확정됩니다. 이에 따라, 치즈가 녹으면서 일부 내부 공기가 바깥과 연결될 수 있습니다. 공기 탐색을 다시합니다.
즉 이를 효율적으로 구현하기 위해서는 치즈를 담는 큐, 공기를 담는 큐 두개를 동시에 사용하면 편리할 것입니다.
코드
# idea / 오히려 공기를 판단한다.
# 치즈 칸을 모두 저장한 다음. 치즈 칸을 모두 또 bfs를 한다.
# # 바깥 칸이 두개 이상일 경우에는 무조건 치즈를 제거하고, 해당 맵을 3으로 교체
# 그리고, 새 좌표를 air_list로 넣어서, 또 탐색 그리고 반복한다.
import sys
from collections import deque
input = sys.stdin.readline
mv_list = [[1, 0], [-1, 0], [0, 1], [0, -1]]
def cheese_control(cheese_queue, maps):
# 치즈가 녹는지 확인. 녹지 않은 치즈 개수를 유지하기 위해 전역변수 고려.
global left_cheese
cur_try = left_cheese
del_cheese = []
for _ in range(cur_try):
cx, cy = cheese_queue.popleft()
cur_cnt = 0
for mv in mv_list:
nx, ny = cx + mv[0], cy + mv[1]
if 0 <= nx < rows and 0 <= ny < cols:
if maps[nx][ny] == 3:
cur_cnt += 1
if cur_cnt >= 2:
del_cheese.append([cx, cy])
left_cheese -= 1
air_queue.append([cx, cy]) # 녹은 치즈는 외부 공기가 된다.
else:
cheese_queue.append([cx, cy])
# 녹을 치즈를 모두 한번에 확인한 다음에 지도에 반영해야 한다.
for dx, dy in del_cheese:
maps[dx][dy] = 3
return maps
def air_bfs(visited, air_queue, maps):
while air_queue:
cx, cy = air_queue.popleft()
for mv in mv_list:
nx, ny = cx + mv[0], cy + mv[1]
if 0 <= nx < rows and 0 <= ny < cols:
# 현재 외부인데, 외부로 적용되지 않은 공기는 0번이다.
if not visited[nx][ny] and maps[nx][ny] == 0:
maps[nx][ny] = 3
visited[nx][ny] = True
air_queue.append([nx, ny])
return maps
rows, cols = map(int, input().split())
maps = []
air_queue = deque()
cheese_queue = deque()
for i in range(rows):
cur_row = list(map(int, input().split()))
for j in range(cols):
if cur_row[j] == 1:
cheese_queue.append([i, j])
elif [i, j] in ([0, 0], [0, cols-1], [rows-1, 0], [rows-1, cols-1]):
cur_row[j] = 3 # 바깥 공기는 3이다.
air_queue.append([i, j])
maps.append(cur_row)
left_cheese = len(cheese_queue)
visited = [[False for _ in range(cols)] for _ in range(rows)]
for [i, j] in ([0, 0], [0, cols-1], [rows-1, 0], [rows-1, cols-1]):
visited[i][j] = True
day = 0
while left_cheese > 0:
maps = air_bfs(visited, air_queue, maps)
maps = cheese_control(cheese_queue, maps)
day += 1
print(day)