[BOJ] 2573번 빙산 - python

문제

2573번: 빙산

 

---

풀이

from collections import deque


def solution(board, n, m):
    year = 0
    while get_num_pieces(board, n, m) < 2:
        board = get_melted_board(board, n, m)
        year += 1
        if is_failed(board, n, m):
            return 0
    return year


def is_failed(board, n, m):
    for i in range(n):
        for j in range(m):
            if board[i][j] != 0:
                return False
    return True


def get_melted_board(board, n, m):
    result = [[0] * m for _ in range(n)]
    dr = [0, 0, 1, -1]
    dc = [1, -1, 0, 0]

    for r in range(n):
        for c in range(m):
            if board[r][c] == 0:
                continue
            melted = 0
            for k in range(4):
                nr, nc = r + dr[k], c + dc[k]
                if 0 <= nr < n and 0 <= nc < m and board[nr][nc] == 0:
                    melted += 1
            result[r][c] = max(0, board[r][c] - melted)
    return result


def get_num_pieces(board, n, m):
    cnt_piece = 0
    visited = [[False] * m for _ in range(n)]

    for r in range(n):
        for c in range(m):
            if board[r][c] != 0 and not visited[r][c]:
                bfs(board, visited, r, c, n, m)
                cnt_piece += 1
    return cnt_piece


def bfs(board, visited, start_r, start_c, n, m):
    dr = [0, 0, 1, -1]
    dc = [1, -1, 0, 0]
    queue = deque()
    queue.append((start_r, start_c))
    visited[start_r][start_c] = True

    while queue:
        r, c = queue.popleft()
        for k in range(4):
            nr, nc = r + dr[k], c + dc[k]
            if 0 <= nr < n and 0 <= nc < m and not visited[nr][nc] and board[nr][nc] != 0:
                queue.append((nr, nc))
                visited[nr][nc] = True


N, M = map(int, input().split())
iceberg = [list(map(int, input().split())) for _ in range(N)]
print(solution(iceberg, N, M))

 

해당 코드는 빙산이 언제 다 녹을지 계산하는 함수를 구현한 것이다. 주어진 N x M 크기의 빙산(board)이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하려고 한다.

 

먼저 get_num_pieces 함수는 빙산의 덩어리 개수를 세는 함수다. 이 함수는 주어진 board를 탐색하면서 빙산의 덩어리를 찾고, 각 빙산의 위치에서 상하좌우로 이어진 빙산을 찾기 위해 bfs 함수를 호출한다. bfs 함수는 너비 우선 탐색(BFS)을 수행하여 빙산이 이어져 있는 위치를 탐색하고, 이를 통해 덩어리 개수를 세는 역할을 한다.

 

is_failed 함수는 board가 모두 0으로 이루어져 있는지 확인하는 함수이다. 모두 0인 경우에는 빙산이 다 녹았음을 의미하므로, 이 함수는 True를 반환한다.

 

get_melted_board 함수는 각 빙산의 주위에 인접한 바닷물의 개수를 계산하여 녹은 빙산의 상태를 갱신하는 함수이고, 빙산의 위치를 탐색하면서 상하좌우를 확인하여 주위에 있는 바닷물의 개수를 세고, 이를 이용하여 빙산의 높이를 조정한다.

 

마지막으로 solution 함수는 위의 함수들을 사용하여 빙산이 다 녹을 때까지 걸리는 시간(년도)을 계산하는 함수이다. 주어진 board에서 빙산의 개수가 2개 미만인 동안 빙산이 녹는 과정을 반복한다. 이 때, get_melted_board 함수를 사용하여 빙산을 녹이고, is_failed 함수를 사용하여 모든 빙산이 다 녹았는지 확인한다. 만약 모든 빙산이 다 녹은 경우에는 0을 반환하고, 그렇지 않은 경우에는 년도를 1 증가시키며 마지막으로 년도를 반환한다.