[Baekjoon] 2573. 빙산

🔗 Problem Link

https://www.acmicpc.net/problem/2573

---

❔Thinking

• 2차원 배열에 빙산의 높이가 주어질 때, 일년마다 상하좌우에 있는 0의 개수만큼 높이가 줄어든다
• 한 덩어리의 빙산이 두개 이상의 덩어리가 되는 최소한의 년수를 반환한다.
• 상하좌우로 붙어 있어야 한 덩어리에 속한다. (즉, 대각선을 포함되지 않는다.)

---

💻Solution

import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
total_ice = sum(cell > 0 for row in board for cell in row)

directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def ice_check():
    """
    현재 board에서 연결된 빙산 덩어리의 수를 반환하는 함수.
    """
    if total_ice == 0:
        return 0

    visited = [[False] * M for _ in range(N)]
    component_count = 0

    for i in range(N):
        for j in range(M):
            if board[i][j] > 0 and not visited[i][j]:
                component_count += 1
                if component_count >= 2:
                    # 두 덩어리가 있으면 더 이상 탐색할 필요 없이 바로 반환
                    return component_count

                # BFS로 연결된 모든 빙산 칸 방문 처리
                queue = deque([(i, j)])
                visited[i][j] = True
                while queue:
                    ci, cj = queue.popleft()
                    for di, dj in directions:
                        ni, nj = ci + di, cj + dj
                        if 0 <= ni < N and 0 <= nj < M:
                            if board[ni][nj] > 0 and not visited[ni][nj]:
                                visited[ni][nj] = True
                                queue.append((ni, nj))
    return component_count

def ice_melting():
    """
    각 빙산 칸 주변의 물의 개수만큼 빙산이 녹는 것을
    동시에 반영하여 board를 갱신하는 함수.
    """
    global total_ice
    # 녹아야 할 칸과 그때 녹는 양을 저장할 리스트
    melting = []
    
    # 전체 board를 순회하며 녹는 양 계산
    for i in range(N):
        for j in range(M):
            if board[i][j] > 0:
                water_count = 0
                for di, dj in directions:
                    ni, nj = i + di, j + dj
                    if 0 <= ni < N and 0 <= nj < M:
                        if board[ni][nj] == 0:
                            water_count += 1
                if water_count:
                    melting.append((i, j, water_count))
    
    # 동시에 녹이기 위해 미리 계산한 녹는 양을 반영
    for i, j, water in melting:
        new_height = board[i][j] - water
        if new_height <= 0:
            if board[i][j] > 0:
                total_ice -= 1
            board[i][j] = 0
        else:
            board[i][j] = new_height

year = 0
while total_ice:
    year += 1
    ice_melting()
    if ice_check() >= 2:
        print(year)
        break
else:
    print(0)

---

🗝️keypoint

1. 주변의 0의 개수를 파악해 곧바로 높이를 수정하면, 새롭게 0이 되는 빙산에 따라 주변 빙산의 높이가 영향을 받는다.
2. while, for문에는 else를 두어 끝까지 반복문을 수행한 경우의 행동을 정의할 수 있다.