소스코드
import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().strip().split())
graph = []
for _ in range(N):
graph.append(list(map(int, input().strip().split())))
d_row = [-1,1,0,0]
d_col = [0,0,-1,1]
# 한 덩이러 전체를 방문하고 처리하는 함수
def bfs(start, visited, graph):
queue = deque([start])
while queue:
r, c = queue.popleft()
for i in range(4):
nr, nc = r + d_row[i], c + d_col[i]
if (0 <= nr < N) and (0 <= nc < M) and (not visited[nr][nc]) and (graph[nr][nc] != 0):
# 방문처리, 큐에 인접노드 넣기
visited[nr][nc] = True
queue.append((nr, nc))
def melt(graph):
new_graph = [[0] * M for _ in range(N)]
for i in range(N):
for j in range(M):
if graph[i][j] > 0:
for k in range(4):
n_row, n_col = i + d_row[k], j + d_col[k]
if 0 <= n_row < N and 0 <= n_col < M and graph[n_row][n_col] == 0:
new_graph[i][j] += 1
for i in range(N):
for j in range(M):
graph[i][j] = max(0, graph[i][j] - new_graph[i][j]) # 빙산 녹은 양만큼 기존 그래프에 적용
time = 0
while True:
iceberg_count = 0
visited = [[False] * M for _ in range(N)]
# 덩어리 개수 세기 : 아직 방문 안 한 지점이 있으면 덩어리 개수를 증가시키고 인접한 칸들도 방문처리
for i in range(N):
for j in range(M):
if graph[i][j] > 0 and not visited[i][j]:
iceberg_count += 1
visited[i][j] = True
bfs((i, j), visited, graph)
# 만약 덩어리가 0개라면 종료
if iceberg_count == 0:
print(0)
break
elif iceberg_count > 1:
print(time)
break
# 빙산 녹이기
melt(graph)
# 시간 증가
time += 1
Python
복사
풀이
•
1년마다 빙하를 녹이고 빙하 덩어리가 2개 이상으로 갈라졌는지 체크해줘야한다는 생각이 들겁니다.
◦
언제 끝날 지는 모르기 때문에, while True 를 이용해서 무한 반복하면서, 일정 조건을 충족하면 while 문을 탈출하도록 작성합니다.
◦
반복문 내에서의 과정은 다음과 같습니다 :
▪
얼음 덩어리의 개수를 BFS를 이용해서 확인합니다.
•
탐색 후 덩어리가 0개이거나 2개 이상이면 결과를 출력하고 반복문을 탈출합니다(끝!!).
•
덩어리가 아직 하나라면, 빙산을 녹입니다 :
◦
(중요 포인트) 빙산을 녹일 때, 한꺼번에 녹은 결과를 반영해야합니다. 그렇기 때문에 녹은 정도를 나타내는 맵을 하나 임시로 만들고, 마지막에 한꺼번에 순회하면서 결과를 반영합니다.
•
time 변수를 1 증가시킵니다.
▪
반복합니다.
회고
•
melt 함수에서 맵을 하나 더 만들고 이를 한타임에 한꺼번에 반영하는 식으로 하지 않고 계속 맵을 안 나가고, 방문한 적 없고, 높이가 1이상인 경우 에 대해 차례대로 높이를 낮추며 큐에 삽입하는 형태로 코드를 작성하고 틀렸습니다. 이러한 방식은 높이가 1이 되어 바다로 변해버리면, 바로 옆 칸의 얼음 높이도 바닷물로 변한 인접 노드의 영향으로 인해 높이가 가속된 채로 낮아지게 됩니다. 그렇기에 각 칸의 높이는 1년마다 한꺼번에 반영되어야 한다는 것을 계속 떠올리지 못해 시간을 많이 잡아먹었습니다.
◦
1년마다 한꺼번에 갱신되어야하는 로직에 대해 보통의 BFS 로직을 그대로 아무 생각없이 사용하지 않도록 주의할 필요가 있겠다는 생각을 했습니다.