백준 2573번 : 빙산 in Python

2573번: 빙산

 

www.acmicpc.net

이 문제는 한 덩어리의 빙산이 주어질 때 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 문제이다. 1년의 시간이 지났을 때 빙산 내 각 칸의 높이는 그 칸이 동서남북으로 이웃한 칸 중 빙산이 없는 칸의 수만큼 감소한다.

이 문제는 복잡해 보이지만 결국 구현해야 하는 것은 크게 현재 시점에서 빙산의 개수를 세는 함수와, 1년의 시간이 지났을 때 빙산의 변화를 구현하는 함수로 나눌 수 있다.

우선 현재 시점에서 빙산의 개수를 세는 것은 주어진 행렬을 바탕으로 그래프 탐색을 수행하면 쉽게 얻을 수 있다. 즉, 행렬 내 모든 entry를 순회하면서 값이 양수인 지점을 찾아 그 지점을 시작으로 너비 우선 탐색(또는 깊이 우선 탐색)을 시행해 그 지점을 포함하는 빙산을 찾고, 빙산의 개수를 1만큼 증가시킨다. 이는 일반적인 그래프 탐색 문제에서 많이 다루었으므로 자세한 구현은 아래 코드에 남긴다.

그 다음 1년의 시간이 지났을 때 빙산의 변화를 구현해야 한다. 이를 위해 우선 주어진 행렬을 복사해 temp라는 행렬을 만든 뒤, 모든 entry를 순회하면서 각 지점 A에 빙산이 있는 경우 그 빙산 주변에 빙산이 없는 칸이 있을 경우 temp 행렬에서 A에 대응하는 지점의 값을 1 감소시킨다. 단, A에 대응하는 지점의 값이 0이 된 경우 A에 빙산이 없다는 의미이므로 이를 그만둔다. 

이 두 함수를 구현한 뒤 빙산의 개수와 연도를 저장하는 변수 cnt와 year를 만들고 초기값을 1, 0으로 한다. 그리고 cnt가 양수인 전제 하에 while loop을 돌면서 우선 cnt를 0으로 만든 뒤 주어진 행렬의 모든 entry에 대해 각 지점에 빙산이 존재하는 경우 cnt를 1 증가시키고 BFS 함수를 수행한다. 이 결과 만약 cnt가 1보다 크다면, 즉 빙산이 두 덩어리 이상 존재하는 경우 while loop을 빠져 나온다. 그렇지 않다면 year를 1 증가시키고 1년의 시간이 지났을 때 빙산의 변화를 구해 주어진 행렬에 덧씌워 저장한다.

이러한 방식으로 진행하다보면 빙산이 두 덩어리 이상이 되어 while loop을 빠져나오거나, 아니면 빙산이 모두 녹아버려 cnt = 0이 되어 while loop을 빠져나오게 된다. 이때 만약 cnt가 1보다 크면 빙산이 두 덩어리 이상이 되어 while loop을 빠져나왔음을 의미하므로 year를 출력하면 된다. 그렇지 않으면 cnt = 0이 되어 while loop을 빠져나왔으므로 이 경우에는 0을 출력한다.

이를 코드로 구현하면 다음과 같다.

from collections import deque
N, M = map(int, input().split())
iceberg = []
for _ in range(N):
    iceberg.append(list(map(int, input().split())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# iceberg 내 각 지점에 빙산이 있는 경우 그 지점을 기준으로 BFS를 수행하는 함수
def BFS(i, j, cur_ice):
    global N, M
    queue = deque()
    queue.append([i, j])
    visited[i][j] = True
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            next_x = x + dx[i]
            next_y = y + dy[i]
            if 0<=next_x<N and 0<=next_y<M and not visited[next_x][next_y] and iceberg[next_x][next_y] > 0:
                visited[next_x][next_y] = True
                queue.append([next_x, next_y])
# 1년의 시간이 지났을 때 빙산의 변화를 반환하는 함수
def melt(iceberg):
    temp = [[0]*M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            temp[i][j] = iceberg[i][j]
    for x in range(N):
        for y in range(M):
            if iceberg[x][y] > 0:
                for i in range(4):
                    next_x = x + dx[i]
                    next_y = y + dy[i]
                    if 0<=next_x<N and 0<=next_y<M and iceberg[next_x][next_y] == 0:
                        temp[x][y] -= 1
                    if temp[x][y] == 0:
                        break
    return temp
# 빙산이 두 덩어리 이상이 될 때까지 지난 시간을 저장하는 변수
year = 0
# 빙산의 개수를 저장하는 변수
cnt = 1
while cnt > 0:
    cnt = 0
    # BFS 구현을 위해 만드는 각 지점을 방문했는지를 저장하는 행렬
    visited = [[False]*M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            if not visited[i][j] and iceberg[i][j] > 0:
                cnt += 1
                BFS(i, j, iceberg)
    if cnt > 1:
        break
    year += 1
    iceberg = melt(iceberg)
if cnt > 1:
    print(year)
else: print(0)