백준 - 빙산 / Gold 4 / 2573번 / Python

문제 📋

백준 - 빙산

풀이 📝

import sys


def melt(ice):
    delta = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    water_cnt = [[0] * m for _ in range(n)]

    for row, col in ice:
        for i in range(4):
            delta_row, delta_col = delta[i]

            new_row = row + delta_row
            new_col = col + delta_col

            if new_row < 0 or new_row >= n or new_col < 0 or new_col >= m:
                continue

            if north_pole[new_row][new_col] == 0:
                water_cnt[row][col] += 1

    for row, col in ice:
        north_pole[row][col] -= water_cnt[row][col]
        if north_pole[row][col] < 0:
            north_pole[row][col] = 0


def dfs(row, col):
    delta = [(1, 0), (0, 1), (-1, 0), (0, -1)]

    for i in range(4):
        delta_row, delta_col = delta[i]

        new_row = row + delta_row
        new_col = col + delta_col

        if new_row < 0 or new_row >= n or new_col < 0 or new_col >= m:
            continue

        if not visited[new_row][new_col] and north_pole[new_row][new_col] > 0:
            visited[new_row][new_col] = True
            dfs(new_row, new_col)
    return


def solution(n, m, north_pole):
    global visited
    year = 0

    while True:
        ice = []
        visited = [[False] * m for _ in range(n)]

        for i in range(n):
            for j in range(m):
                if north_pole[i][j] > 0:
                    ice.append((i, j))
        if not ice:  # 모두 녹았다면
            break

        dfs(ice[0][0], ice[0][1])  # DFS로 이어진 부분을 다 탐색했는데

        for row, col in ice:
            if not visited[row][col]:  # 얼음이 남아있다면
                return year  # 빙산이 분리된 것이다.

        melt(ice)
        year += 1

    return 0


sys.setrecursionlimit(10**6)
n, m = map(int, sys.stdin.readline().split())
north_pole = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
print(solution(n, m, north_pole))

크게 어렵지 않은 그래프 탐색 문제였다.
다음과 같이 크게 2가지로 나눠서 개발했다.

1. 빙산이 녹는 현상 구현 : melt()
   • 1 이상인 좌표들의 상하좌우를 보면서 0을 카운팅하고 딕셔너리에 저장
   • 1 이상인 좌표들 순회하면서 딕셔너리 값만큼 빼준다.
   • year += 1
2. 빙산 개수 세기 구현
   • 1 이상인 좌표들 중 하나에서 DFS 탐색 실행.
   • 1 이상인 좌표들 중 아직 탐색 안한 곳이 있다면 빙산이 분리된 것.

고려할 점

• 시간 복잡도 측면에서 봤을 때도 1 이상인 좌표의 개수가 최대 10,000이기 때문에 문제없었다.
• melt()는 엄연히 판단하면 BFS는 아니라고 생각한다. 왜냐하면 가까운 노드를 계속해서 탐색해 나가는 게 아닌 단순하게 1 이상의 좌표들의 상하좌우만 탐색하기 때문이다.
• 빙산 개수 세기 구현에선 굳이 DFS 사용 안 하고 BFS 사용해도 된다고 생각한다.