[Python] 백준 2573번 빙산

이번에 풀어볼 문제는 빙산 문제이다. 시간이 지나면서 입력으로 주어진 빙산이 녹아가는데, 빙산이 처음으로 분리되는 시간을 구하는 문제이다. 문제의 조건은 아래와 같다. 

 

• 빙산이 상하좌우로 맞닿아 있는 바닷물의 칸수만큼 녹는다. 
• 빙산이 차지하는 칸의 개수는 최대 10,000개이다. 
• 배열의 첫 번째 행과 마지막 행, 첫 번째 열과 마지막 열에는 빙산이 존재하지 않는다. 
• 빙산의 높이는 최대 10이다. 

기본적인 탐색 문제이다. 먼저 바닷물과 맞닿아 있는 빙산들을 녹이고 나서, 아직 녹지 않은 빙산을 기준으로 탐색을 진행하여 연결된 빙산들을 모두 방문처리 해주는 방식이다. 이렇게 탐색이 한 번 진행된 이후에도 아직 방문하지 않은 빙산이 존재한다면, 빙산이 둘 이상으로 갈라지게 된 것이므로 탐색을 종료한다. 

 

다만 이 문제를 풀때 주의해야 할 점이 몇 가지 있다.

1. 빙산을 녹일때, 같은 시간에 녹은 빙산에 의해 다른 빙산이 녹는 정도에 영향을 끼치면 안 된다. 
2. 빙산이 둘 이상으로 분리되지 않고 한번에 다 녹아버리는 경우가 존재한다. 

1번 같은 경우는 아래의 그림과 같다. 

위와 같은 상황을 가정해보자. 이제 바닷물과 맞닿아 있는 빙산들은 녹게 되는데, 낮아지는 높이를 계산해 보면 아래와 같다. 

위와 같은 상황에서 이제 빙산을 하나씩 다시 검사해가며 높이만큼 빙산을 지워주면 된다. 하지만 구현을 할 때에는 빙산이 맞닿아 있는 바닷물 칸의 개수를 세어주고, 바로 빙산을 지워버리는 경우가 있는데, 이는 다음과 같은 상황을 발생시킬 수 있다. 

 

이 그림은 이전 그림에서 맨 위의 칸부터 빙산이 맞닿아 있는 바닷물 칸의 개수를 세어주고, 그만큼 지우면서 내려온 결과이다. 맨 가운데 1 또한 왼쪽의 1이 지워진 이후에 바닷물 검사를 진행하기 때문에 지워지게 되고, 맨 왼쪽 아래의 3도 바닷물 칸의 개수가 원래 2개에서 3개로 증가해 지워지게 될 것이다. 이런 식으로 구현을 하게 되면 완전히 잘못된 답을 구할 수 있다. 

 

 

2번째 문제는 위의 그림과 같은 상황이다. 아직은 빙산이 한 덩어리이지만, 시간이 한 번 지나고나면 모든 빙산이 녹아버린다. 문제에서는 이런 경우 0을 출력하라고 했으므로 이를 판별하는 것이 필요할 것이다. 

 

이제 코드를 하나하나 살펴보자.

dic = {}
for i in range(n):
    for j in range(m):
        if world[i][j] > 0:
            dic[(i, j)] = world[i][j]

맨처음에 빙산이 있는 위치를 찾아 위치를 키 값으로 하고, 빙산의 높이를 value로 하는 딕셔너리를 만들어준다. 

 

time = 1
while True:
    loop = list(dic.keys())
    # 빙산이 녹아내리는 값 계산
    for y, x in loop:
        cnt = 0
        for d in range(4):
            ny, nx = y+dy[d], x+dx[d]
            if 0 <= ny < n and 0 <= nx < m:
                if world[ny][nx] == 0:
                    cnt += 1
        dic[(y,x)] -= cnt
        
    # 빙산을 실제로 녹임
    not_exist = True
    for y, x in loop:
        if dic[(y, x)] <= 0: 
            world[y][x] = 0
            dic.pop((y, x))
        else:
            not_exist = False
    if not_exist:
        print(0)
        break
        
    # 빙산이 분리되었는지 검사
    visited = [[0] * m for _ in range(n)]
    cnt_bfs = 0
    for y, x in dic.keys():
        if not visited[y][x]:
            if cnt_bfs == 1:
                cnt_bfs += 1
                break
            bfs(y, x, visited)
            cnt_bfs += 1
    if cnt_bfs > 1:
        print(time)
        break
    time += 1

이후 while문 안에서 time을 1씩 증가시키며 순서대로 빙산이 녹아내리는 값을 계산하고, 계산한 값을 바탕으로 실제 빙산을 녹이는 작업을 하고, 마지막으로 빙산이 분리되었는지를 검사한다. 만약 딕셔너리가 모두 비었으면 not_exist 변수가 True로 설정되어 0을 출력하고 종료하게 된다. 빙산이 이어져있는지에 대한 탐색은 BFS를 활용하였다.

 

마지막으로 전체 코드는 다음과 같다. 

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

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

n, m = map(int, input().split())

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

def bfs(y, x, visited):
    deq = deque()
    deq.append((y, x))
    while deq:
        y, x = deq.popleft()
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < n and 0 <= nx < m:
                if not visited[ny][nx] and world[ny][nx] > 0:
                    visited[ny][nx] = 1
                    deq.append((ny, nx))

dic = {}
for i in range(n):
    for j in range(m):
        if world[i][j] > 0:
            dic[(i, j)] = world[i][j]
            
time = 1
while True:
    loop = list(dic.keys())
    for y, x in loop:
        cnt = 0
        for d in range(4):
            ny, nx = y+dy[d], x+dx[d]
            if 0 <= ny < n and 0 <= nx < m:
                if world[ny][nx] == 0:
                    cnt += 1
        dic[(y,x)] -= cnt 
    not_exist = True
    for y, x in loop:
        if dic[(y, x)] <= 0: 
            world[y][x] = 0
            dic.pop((y, x))
        else:
            not_exist = False
    if not_exist:
        print(0)
        break
    visited = [[0] * m for _ in range(n)]
    cnt_bfs = 0
    for y, x in dic.keys():
        if not visited[y][x]:
            if cnt_bfs == 1:
                cnt_bfs += 1
                break
            bfs(y, x, visited)
            cnt_bfs += 1
    if cnt_bfs > 1:
        print(time)
        break
    time += 1