[백준 - Python] 2573. 빙산 (DFS/BFS)

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

2573번: 빙산

 

코드

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

def bfs(x, y):
    q = deque([(x, y)])
    visited[x][y] = 1
    seaList = []

    while q:
        x, y = q.popleft()
        sea = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if not graph[nx][ny]:  # 상하좌우 중 바다이면
                    sea += 1
                elif graph[nx][ny] and not visited[nx][ny]:  # 방문하지 않은 빙산이면
                    q.append((nx, ny))                      # 탐색
                    visited[nx][ny] = 1                     # 방문 처리

        if sea > 0:         # 한 빙산에 대해 상하좌우 모두 탐색했는데, 바다가 하나라도 있으면, seaList에 좌표값과 바다 개수 튜플로 저장
            seaList.append((x, y, sea))

    for x, y, sea in seaList:  # 빙산 녹이기
        graph[x][y] = max(0, graph[x][y] - sea) # max 함수로 음수가 되면 0으로 (분기 X)

    return 1

ice = []
for i in range(n):
    for j in range(m):
        if graph[i][j]: # 바다가 아니면
            ice.append((i, j))  # 빙산이 존재하는 위치 좌표만 ice에 저장

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

while ice:  # 빙산이 존재하는 동안
    visited = [[0] * m for _ in range(n)]
    delList = []
    group = 0
    for i, j in ice:  # 각각의 빙산에 대해서
        if graph[i][j] and not visited[i][j]:  # 방문하지 않은 빙산인 경우
            group += bfs(i, j)  # 탐색 시작
        if graph[i][j] == 0:   # 탐색이 끝나고, 해당 빙산이 바다가 되었으면, 제거 리스트에 저장
            delList.append((i, j))
    if group > 1:
        print(year)
        break

    ice = sorted(list(set(ice)-set(delList)))  # 바다가 된 빙산은 탐색하지 않아도 됨으로 ice 에서 제거
    year += 1

# 빙산이 전부 녹을 때까지 분리되지 않은 경우
if group < 2:
    print(0)

 

 

2차원 배열을 탐색하기 때문에

방문 여부를 확인하는 변수도 2차원 배열로 선언해 주어야 한다.

 

이 문제의 핵심 아이디어는

바다와 맞닿아있는 빙산을 탐색하면서 녹이면 안 되고,

시간 한번이 다 지나고 나서 한번에 녹여줘야

같은 시간 내의 다른 빙산 주변 바다를 카운팅 할 때,

카운팅이 올바르다.

 

시간이 지나고 한번에 빙산을 녹이는 방법,

즉, 한 타임이 지나기 전에 빙산 별로 주변에 바다가 몇 개 있는지를

어떤 식으로 저장하고 관리할 지가 관건인 것 같다.

 

정답 코드에서는

빙산이 존재하는 위치 좌표를 튜플 형태로 ice라는 리스트에 저장해서 관리하였고,

탐색을 돌면서 ice에 있는 빙산들이 바다로 변했는지 시간이 지남에 따라 체크해주었다.

 

bfs 함수에서는 시작 빙산부터 상하좌우를 탐색하면서,

바다이면 sea 함수를 1 증가시켜

주변 바다의 개수를 카운팅 해주었다.

방문하지 않은 빙산이면, 큐에 넣고 방문 처리를 해주어 탐색을 해주었다.

 

네 방향에 대한 탐색을 마친 후,

바다가 하나라도 존재하는 경우,

해당 위치 좌표와 바다 개수를 튜플 형태로 seaList에 담아 관리하였고

 

큐가 다 비었을 경우,

덩어리 하나에 대한 탐색이 끝난 것임으로

앞선 바다 개수를 담고 있는 seaList를 활용해

빙산을 한번에 녹여주었다.

 

덩어리는 바다로 둘러쌓여 있기 때문에

같은 시간 내에서 덩어리 단위로 빙산을 녹여도 되기 때문에

bfs 단위 별로 빙산을 녹이는 코드를 넣어주어도 무방하다.

 

이때, 좌표값과 바다 개수를 같이 저장해주었기 때문에,

빙산의 높이가 저장되어 있는 graph 변수에

쉽게 접근하고 값을 수정할 수 있었다.

 

튜플은 꼭 원소가 2개일 필요가 없고

필요한 만큼 요소를 넣어 유용하게 활용할 수 있음을 깨달을 수 있는 문제였다.

 

마지막에 리스트를 set 자료구조로 변환해,

원하는 요소들만 삭제하는 코드도

눈 여겨서 봐두면 좋을 것 같다.

 

 

[참고 자료]

https://velog.io/@hygge/Python-%EB%B0%B1%EC%A4%80-2573-%EB%B9%99%EC%82%B0-BFS