Concept & Process (BFS)

• 매년마다 graph 전체를 탐색
• 아직 방문하지 않은 빙산일 경우, 그 칸을 기점으로 bfs 탐색함으로써 빙산의 높이를 조정함
• bfs 탐색한 횟수(bfs_cnt)에 따라 다음 할 행동을 결정
  • 만약 1번만 탐색했다면, 빙산 덩어리가 하나임을 의미하므로, 내년으로 넘어감
  • 만약 2번 이상 탐색했다면, 빙산 덩어리가 여러 개임을 의미하므로, 탐색을 멈추고 결과값을 출력
  • 만약 0번 탐색했다면, 빙산이 다 녹아 없다는 것을 의미하므로, 0을 출력

Point

빙산이 녹아서 변한 빙산 높이를 바로 graph에 적용하면 안된다.

• 만약 빙산 덩어리 외곽에 있는 칸이 녹아서 0이 되었다고 가정해보자.
  • 그렇다면 그 칸과 인접한 칸을 방문해서 빙산의 높이를 재조정할 때,
    전 칸이 0이 되어버렸기 때문에 필요보다 더 많이 빙산 높이를 줄이게 될 것이다.
• 이것은 문제가 정의한 녹는 방식이 아니므로,
  이를 방지하기 위해 해마다 기존 graph 값을 유지하되,
  new_graph에다가 새로운 빙산 높이들을 저장하고,
  그 해의 graph를 모두 탐색 한 후 new_graph 값들로 graph를 업데이트해줘야 한다.

코드

import sys
from collections import deque
from itertools import product

input = sys.stdin.readline

def bfs(s_x, s_y):
     global graph, visited, new_graph
     q = deque([[s_x, s_y]])
     dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
     while q:
          x, y = q.popleft()
          if not visited[x][y]:
               visited[x][y] = True
               water_cnt = 0
               for i, j in zip(dx, dy):
                    n_x, n_y = x+i, y+j
                    if graph[n_x][n_y]:
                         q.append([n_x, n_y])
                    else:
                         water_cnt += 1
                    new_graph[x][y] = graph[x][y] - water_cnt if graph[x][y] >= water_cnt else 0

if __name__ == '__main__':
     N, M = map(int, input().split())
     graph = [list(map(int, input().split())) for _ in range(N)]
     years = 0
     
     while True:
          visited = [[False for _ in range(M)] for _ in range(N)]
          new_graph = [[0 for _ in range(M)] for _ in range(N)]
          bfs_cnt = 0
          
          for s_x, s_y in product(range(N), range(M)):
               if graph[s_x][s_y] and not visited[s_x][s_y]:
                    bfs(s_x, s_y)
                    bfs_cnt += 1
          graph = new_graph   
          if bfs_cnt == 0:
               print(0)
               exit()
          elif bfs_cnt > 1:
               print(years)
               exit()
          years += 1