[🥇4 / 백준 2573 / 파이썬] 빙산

 

2573번: 빙산

 

문제

지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.

 

그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에 저장된 빙산의 높이 정보

빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 따라서 그림 1의 빙산은 일년후에 그림 2와 같이 변형된다.

그림 3은 그림 1의 빙산이 2년 후에 변한 모습을 보여준다. 2차원 배열에서 동서남북 방향으로 붙어있는 칸들은 서로 연결되어 있다고 말한다. 따라서 그림 2의 빙산은 한 덩어리이지만, 그림 3의 빙산은 세 덩어리로 분리되어 있다.

 

그림 2

 

그림 3

 

한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.

 

입력

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.

출력

첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.

 

예제 입력  5 7 0 0 0 0 0 0 0 0 2 4 5 3 0 0 0 3 0 2 5 2 0 0 7 6 2 4 0 0 0 0 0 0 0 0 0

예제 출력  2

 

풀이

 

빙산이 두 개 이상으로 분리되는데까지 걸리는 시간을 출력하는 문제이다.

 

우선 매번 for문으로 지도 전체에서 빙산이 있는 좌표를 구하는 것은 굉장히 연산을 많이 소비할 것 같았다.

따라서 처음에 한 번만 for문을 돌아 빙산의 좌표를 담은 배열(pos)을 만들었다.

이제 이 좌표에서만 for문을 돌아 줄 것이다.

 

주의해야 할 것이 있는데, 실시간으로 빙산을 녹이면 안 된다.

빙산은 한 틱에 전체가 동시에 녹기 때문에, 녹을 곳의 좌표와 얼마나 녹을 지를 따로 기록해둔 뒤 처리해주어야 한다.

 

빙산을 녹였으면, 이제 빙산이 분리되었는지 체크해야 한다.필자는 BFS로 영역 탐색을 진행했다.마찬가지로 맵 전체를 다시 for문으로 돌며 빙산의 좌표를 구하지 않는다. 그냥 아까 구했던 pos 배열에서 아무거나 하나 가져와서 진행하면 된다.

 

BFS를 하며 그 영역에서 빙산의 개수를 세고, pos 배열과 이 수치가 다르면 빙산이 하나 이상 떨어져 나간 것이다.이 때 현재 틱을 출력하고 시스템을 종료하도록 하자.

 

만약 pos 배열이 빌 때까지 분리가 되지 않았다면 0을 출력하면 된다.

 

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

def bfs():
    visit_tmp = [i[:] for i in visit]
    tmp = pos.pop(); pos.add(tmp)
    q = deque([tmp])
    a,b = tmp
    visit_tmp[a][b] = True
    cnt = 1
    while q:
        x,y = q.popleft()
        for a,b in move:
            dx=x+a; dy=y+b
            if visit_tmp[dx][dy] or not board[dx][dy]:
                continue
            visit_tmp[dx][dy] = True
            cnt+=1
            q.append((dx,dy))
    
    # 빙산 분리, 종료
    if cnt != len(pos):
        print(t)
        sys.exit()

n,m = map(int,input().split())
board = [list(map(int,input().split())) for _ in range(n)]
pos = set()
for i in range(1,n):
    for j in range(1,m):
        if board[i][j] > 0:
            pos.add((i,j))

move = [(0,1),(1,0),(0,-1),(-1,0)]
t = 0
melt = [[0]*m for _ in range(n)]
visit = [[False]*m for _ in range(n)]

# 이미 처음부터 분리돼있을 가능성.
# 하지만 첫 bfs를 빼도 AC를 받는 것 보니, 무조건 합쳐진 상태로 입력이 주어지나 보다.
bfs()

# 해빙 시작
while pos:
    t+=1
    rmpos = []
    # 녹을 수치
    for x, y in pos:
        for a,b in move:
            dx=x+a; dy=y+b
            if not board[dx][dy]:
                melt[x][y] += 1
    
    # 실제 해빙
    for x, y in pos:
        board[x][y] = max(0,board[x][y]-melt[x][y])
        melt[x][y] = 0
        if board[x][y] <= 0:
            rmpos.append((x,y))
            
    for i in rmpos:
        pos.remove(i)
        
    # 영역의 수
    if not pos:
        print(0)
        break
    
    bfs()
else:
    print(0)