[백준 - Python] 2573 - 빙산

0.  문제 링크

 

 

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

2573번: 빙산

---

1.  풀이 방법

 

 

우선 빙산의 녹음을 구현한 함수인 melt()와 그룹화하는 함수인 group() 함수를 구현했다.

그리고 빙산 근처에 바다의 개수를 세는 adj도 따로 만들어서, 빙산 근처에 몇 개의 바다가 있는지 셌다.

melt() 함수를 사용하고, 다시 인접한 바다의 개수를 셌다.

만약 특정 빙산이 모두 녹았다면 해당 빙산은 adj 딕셔너리에서 pop 하였다.

group() 함수에서는 BFS를 사용했고, 모두 한 그룹이 되지 않으면 같은 과정을 반복하였다.

이때 한 그룹이 되는 건 어떻게 알았냐면, 그냥 아무 좌표 하나 잡고 BFS를 하면서 set에 넣는다.

이후 BFS가 끝나고, set과 adj의 길이를 비교했을 때, 같다면 빙산이 하나의 그룹으로 이루어진 것이다.

만약 길이가 다르다면 이는 필연적으로 빙산이 두 개 이상의 그룹으로 나뉜 것이므로 그대로 반환하였다.

---

2.  코드

 

 

import sys
from collections import deque


def melt():
    # 빙산의 녹음을 구현한 함수
    adj_list = list(adj.items())
    for (y, x), cnt in adj_list:
        maps[y][x] = max(maps[y][x] - cnt, 0)
        if maps[y][x] == 0:
            adj.pop((y, x))     # 만약 모두 녹았다면 이제 인접한 바다가 있는지 체크할 필요가 없음

    for (y, x) in adj.keys():
        adj[(y, x)] = 0
        for dy, dx in dir:
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m:
                if maps[ny][nx] == 0:
                    adj[(y, x)] += 1        # 다시 인접한 바다의 개수를 셈


def group():
    if len(adj) == 0:       # 만약 모두 녹기 전까지 분리된 적이 없다면 -1를 반환함
        return -1

    dq.append(list(adj.keys())[0])      # 맨 처음 좌표를 넣음
    check = set()

    while dq:
        y, x = dq.popleft()
        for dy, dx in dir:
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m and (ny, nx) not in check:
                if maps[ny][nx]:
                    dq.append((ny, nx))
                    check.add((ny, nx))

    if len(check) != len(adj):      # 두 개의 개수가 다르면 2덩이 이상으로 나뉘어진 것이므로 그대로 반환함
        return True

    return False


def sol():
    cnt = 1
    while True:
        melt()
        match group():
            case True:
                return cnt
            case False:
                cnt += 1
            case -1:
                return 0


if __name__ == "__main__":
    input = sys.stdin.readline
    n, m = map(int, input().split())
    maps = [[m for m in map(int, input().split())] for _ in range(n)]
    adj = dict()
    dq = deque()

    dir = [[-1, 0], [0, 1], [1, 0], [0, -1]]

    for y in range(n):
        for x in range(m):
            if maps[y][x]:
                adj[(y, x)] = 0
                for dy, dx in dir:
                    ny, nx = y + dy, x + dx
                    if 0 <= ny < n and 0 <= nx < m:
                        if maps[ny][nx] == 0:
                            adj[(y, x)] += 1        # 인접한 바다의 개수를 셈

    print(sol())

---

3.  마무리