[Baekjoon] 빙산(python)

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

문제 접근

오랜만에 정답을 안보고 푼 문제이다.

 

BFS를 이용한 구현문제였다.

 

BFS를 통해 4방향에 인접한 빙산을 탐색하여 빙산의 그룹이 분리되었는지 확인하고 iceberg에 저장된 빙산들을 4방향에 인접한 물의 갯수만큼 빙산의 높이를 빼주면 된다.

---

풀이 과정

1. 빙산이 분리되었는지 확인

빙산의 위치에서 BFS를 통해 방문한 위치의 갯수와 미리 iceberg 배열에 저장해두었던 빙산의 위치의 갯수가 같으면 분리되지 않은 것이고 다르면 분리된 것이다.

 

하나의 빙산의 위치에서 BFS를 통해 탐색하면 모든 빙산을 방문할 것이기 때문에 위치의 갯수가 다르면 분리된 것으로 판단한다.

def bfs(x, y):
    visited = [[False] * M for _ in range(N)]

    count = 0

    q = deque()
    q.append([x, y])
    visited[x][y] = True

    while q:
        cur_x, cur_y = q.popleft()
        count += 1

        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]

            if (
                0 <= next_x < N
                and 0 <= next_y < M
                and not visited[next_x][next_y]
                and board[next_x][next_y]
            ):
                q.append([next_x, next_y])
                visited[next_x][next_y] = True

    return count


def is_seperated_iceberg():
    for i in range(N):
        for j in range(M):
            if board[i][j] != 0:
                count = bfs(i, j)

                if count == len(iceberg):
                    return False
                else:
                    return True

 

2. 빙산 녹이기

미리 iceberg에 저쟁해두었던 빙산의 위치에서 4방향으로 탐색해서 물에 인접한 면적의 갯수만큼 빙산의 높이를 빼주면 된다.

빙산의 높이가 0보다 작거나 같으면 iceberg 배열에서 제거한다.

def melt_iceberg():
    global board, iceberg

    tmp = [board[i][:] for i in range(N)]
    remove_list = []

    for x, y in iceberg:
        count = 0

        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]

            if board[nx][ny] == 0:
                count += 1

        tmp[x][y] = max(board[x][y] - count, 0)

        if tmp[x][y] <= 0:
            remove_list.append([x, y])

    board = tmp
    iceberg = list(filter(lambda x: x not in remove_list, iceberg))

---

정답 코드

"""
    백준 2573번 빙산
"""

import sys
from collections import deque


N, M = list(map(int, sys.stdin.readline().split()))
board = []
iceberg = []
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]

for i in range(N):
    board.append(list(map(int, sys.stdin.readline().split())))

    for j in range(M):
        if board[i][j] != 0:
            iceberg.append([i, j])


def bfs(x, y):
    visited = [[False] * M for _ in range(N)]

    count = 0

    q = deque()
    q.append([x, y])
    visited[x][y] = True

    while q:
        cur_x, cur_y = q.popleft()
        count += 1

        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]

            if (
                0 <= next_x < N
                and 0 <= next_y < M
                and not visited[next_x][next_y]
                and board[next_x][next_y]
            ):
                q.append([next_x, next_y])
                visited[next_x][next_y] = True

    return count


def is_seperated_iceberg():
    for i in range(N):
        for j in range(M):
            if board[i][j] != 0:
                count = bfs(i, j)

                if count == len(iceberg):
                    return False
                else:
                    return True


def melt_iceberg():
    global board, iceberg

    tmp = [board[i][:] for i in range(N)]
    remove_list = []

    for x, y in iceberg:
        count = 0

        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]

            if board[nx][ny] == 0:
                count += 1

        tmp[x][y] = max(board[x][y] - count, 0)

        if tmp[x][y] <= 0:
            remove_list.append([x, y])

    board = tmp
    iceberg = list(filter(lambda x: x not in remove_list, iceberg))


def solve():
    result = 0

    while True:

        if is_seperated_iceberg():
            break

        # 빙산이 모두 제거되었는데 분리되지 않으면 0을 반환
        if not iceberg:
            return 0

        result += 1
        melt_iceberg()

    return result


print(solve())