백준: 2573 빙산

문제

2573번: 빙산

 

문제 풀이

 빙산의 높이가 주어질 때, 1년이 지날 때마다 바다에 인접한 수만큼 빙산이 녹아서 없어진다. 이때 빙산의 영역이 2개 이상이 되는 최소의 시간(년)을 찾는 문제이다. 문제를 풀기 위해서는 BFS를 통해 영역을 탐색함과 동시에, 각 빙하가 바다와 인접하고 있는 수를 카운트하여 해결할 수 있다.

 

• BFS를 통해, 빙하인 부분부터 탐색을 시작한다.
  • 빙하 주위가 바다라면, 딕셔너리를 통해 해당 지점을 카운트한다.
• BFS 탐색 후에, 탐색 가능한 영역 (빙하의 영역)이 2개 이상이라면, 즉시 중단하고 반복 횟수를 출력한다.
• 빙하가 하나도 없다면, 0을 출력하고 탐색을 종료한다.
• 빙하가 남아 있고, 영역이 2개 이상이 아니라면 카운트한 딕셔너리를 활용하여 빙하를 녹인다.
• 위의 과정을 빙하가 없거나, 영역을 찾을 때까지 반복한다.

 

코드

from sys import stdin
from collections import deque, defaultdict


def visitable(x, y):
    return 0 <= x < n and 0 <= y < m and not visited[x][y]


def bfs(start):
    ret = defaultdict(int)
    q = deque([start])
    dirs = ((0, 1), (0, -1), (-1, 0), (1, 0))

    while q:
        x, y = q.popleft()

        for dx, dy in dirs:
            next_x, next_y = x + dx, y + dy
            if visitable(next_x, next_y):
                # 주변이 바다인 경우, 바다의 수를 카운트
                if graph[next_x][next_y] == 0:
                    ret[(x, y)] += 1
                # 0이 아니고 빙하인 경우 탐색을 위해 추가
                else:
                    visited[next_x][next_y] = True
                    q.append((next_x, next_y))
    return ret


if __name__ == '__main__':
    n, m = map(int, stdin.readline().split())
    graph = [list(map(int, stdin.readline().split())) for _ in range(n)]

    time = 0

    while True:
        visited = [[False] * m for _ in range(n)]
        iceberg = 0
        for i in range(n):
            for j in range(m):
                if graph[i][j] != 0 and not visited[i][j]:
                    visited[i][j] = True
                    ice = bfs([i, j])
                    iceberg += 1
                    # 빙산이 2개 이상이라면 조건을 만족한 경우
                    if iceberg > 1:
                        print(time)
                        exit(0)

        # 빙산이 하나도 없는 경우, 중단.
        if iceberg == 0:
            time = 0
            break

        # 주변의 바다 수만큼 빙하를 녹임.
        for (i, j), cnt in ice.items():
            graph[i][j] = 0 if graph[i][j] < cnt else graph[i][j] - cnt

        time += 1

    print(time)

 처음에 풀 때는 하나를 탐색하면서 빙하를 바로바로 녹였는데, 그렇게 하면 예제 입력 1에서 문제가 발생한다. 따라서 영역의 수를 확인하는 겸, 빙하를 녹일 수 있는 경우를 카운트하여야 한다.😉