[백준 2573번] 빙산 (Python)

그래프 탐색(DFS, BFS)과 추가적인 구현이 필요한 문제였다.

 

문제 링크

2573번 빙산

 

문제 요약

이 문제는 지구 온난화로 인해 북극의 빙산이 녹고 있는 상황을 배경으로 한다.

빙산을 2차원 배열에 양의 정수로 표시하여, 각 부분별 높이 정보를 배열의 각 칸에 저장한다.

빙산이 아닌 바다에 해당되는 칸에는 0이 저장된다.

빙산의 높이는 동서남북 네 방향으로 0이 저장된 칸의 개수만큼 매년 줄어든다.

한 덩어리의 빙산이 주어졌을 때, 이 빙산이 두 덩어리 이상으로 분리되는 시간(년)을 구하는 것이 문제의 목표.

입력: 첫 줄에는 2차원 배열의 행과 열의 개수(N, M)가 주어지고, 그 다음 N개의 줄에는 M개의 정수가 주어지며, 이는 빙산의 높이 정보

출력: 빙산이 두 덩어리 이상으로 분리되는 최초의 시간을 출력 | 만약 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 0을 출력

 

접근 방법 정리

- 빙산이 2덩로 나뉘었는지 체크가 필요하다 -> BFS로 count를 세어 2개 이상이 되었는지 확인하자 (DFS도 당연 가능)

- 바닷물과 접해있는 빙산을 녹여야한다. -> 동서남북에 바닷물의 갯수를 판단해 새 배열에 넣자

 

코드

import heapq
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
newArr = [[0] * M for _ in range(N)]
visited = [[0] * M for _ in range(N)]

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def bfs(x, y):
    heap = []
    heapq.heappush(heap, (x, y))

    while heap:
        a, b = heapq.heappop(heap)

        ice = 0
        for d in range(4):
            nx = a + dx[d]
            ny = b + dy[d]

            if 0 <= nx < N and 0 <= ny < M:
                if arr[nx][ny] == 0:
                    ice += 1
                if not visited[nx][ny] and arr[nx][ny] != 0:
                    heapq.heappush(heap, (nx, ny))
                    visited[nx][ny] = 1

        newArr[a][b] = 0 if arr[a][b] - ice < 0 else arr[a][b] - ice

year = 0
while True:
    newArr = [[0] * M for _ in range(N)]
    visited = [[0] * M for _ in range(N)]
    count = 0
    zero = True

    for i in range(N):
        for j in range(M):
            if arr[i][j] != 0:
                zero = False
                if not visited[i][j]:
                    bfs(i, j)
                    count += 1

    if count >= 2:
        print(year)
        break
    elif zero:
        print(0)
        break

    year += 1
    arr = newArr

 

더 간결하고 좋은 코드가 있을 것 같긴한데, 많은 변수를 사용한 것 같긴하다!