파이썬 백준 2573 빙산

import sys
input = sys.stdin.readline
from collections import deque
 
n, m = map(int, input().split())
T = []
que = deque()
for i in range(n) : 
    T.append(list(map(int, input().split())) + [None])
    for j in range(m) : 
        if T[i][j] != 0 : 
            que.append([i, j])
T.append([None for i in range(m + 1)])
 
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def cutcheck(ice) : 
    gone = {}
    for a, b in ice : 
        gone[(a, b)] = False
    a, b = ice[0][0], ice[0][1]
    gone[(a, b)] = True
    q = deque()
    q.append([a, b])
    check = 1
    while q : 
        a, b = q.popleft()
        for i in range(4) : 
            x = a + dx[i]
            y = b + dy[i]
            if T[x][y] > 0 and not gone[(x, y)] : 
                gone[(x, y)] = True
                q.append([x, y])
                check = check + 1
    if check != len(ice) : 
        return True
    return False
 
year = -1
que.append(['year', year - 1])
while que : 
    a, b = que.popleft()
    if a != 'year' : 
        count = 0
        for i in range(4) : 
            x = a + dx[i]
            y = b + dy[i]
            if year < T[x][y] <= 0 : 
                count = count + 1
        if T[a][b] > count : 
            que.append([a, b])
            T[a][b] = T[a][b] - count
        else : 
            T[a][b] = year
    else : 
        if len(que) == 0 : 
            print(0)
            exit(0)
        else : 
            if cutcheck(que) : 
                print(-year)
                exit(0)
            else : 
                year = b
                que.append(['year', b - 1])
 

line 5 ~ 13

인풋받은 빙산의 정보를 2차원 행렬 T에 넣는다.

녹지 않은 빙산에 대해 BFS를 돌릴 것이므로 T[i][j]의 값이 0이 아니라면 미리 큐에 넣어둔다.

이후 dx, dy를 이용한 4방향 BFS에서 [-1] 역류를 막기 위해, T의 한쪽 끝 row, col에 None 벽을 만든다.

 

line 15 ~ 34

녹지 않은 좌표들의 집합 ice를 받으면, 빙산이 1개인지 아닌지 T/F를 출력하는 함수 cutcheck을 정의한다.

que에는 아직 안녹은 빙산만 들어가 있으므로, 인풋으로는 que를 그대로 줄 예정이다. (ice = que)

영역이 몇개인지는 중요하지 않고 1개인지 아닌지만 알면 되므로, ice의 모든 점에서 BFS를 실행할 필요는 없다.

아무 점 하나에서 실행하면서, 대신 que에 append할때마다 카운트하여 시작점과 연결된 점의 개수를 센다.

 

line 35 ~ 37

카운트한 점의 갯수가 인풋받은 ice의 원소 수와 같지 않다면, 아직 탐색하지 않은 점이 있다는 의미이다.

즉 영역이 아무튼 1개는 아니라는 의미이니 빙산이 cut된 것이므로, True를 출력한다. 같다면 Flase.

 

line 41 ~ 54

que에서 빙산의 좌표 a, b를 pop받아 이에 인접한 바다의 수를 count하여 T[a][b]의 값을 빼준다.

이때 값이 음수가 되었다면, T[a][b]를 0이 아니라 현재 연도를 음수로 기록한 값 year로 바꿔준다.

즉 원래 빙산이었다가 녹은 좌표들은 언제 녹은 것인지 T에 기록되고, 이를 통해 올해 녹은 빙산이 인접 빙산에 영향을 주는 것을 막을 수 있다. 인접한 좌표가 year 초과 0 이하일 때에만 바다인 것으로 간주하여 count해준다. (line 48)

인접한 바다의 수만큼 빼주고도 T값이 양수라면, 내년에도 체크하기 위해 다시 que에 넣어준다.

 

line 40, line 55~ 62

que에는 초기값으로 0년도 빙산의 좌표들이 담겨있다. 이제 'year'라는 빙산이 아닌 원소를 큐에 넣는다.

이상태로 while que가 실행된다면, 0년도의 모든 빙산이 녹으며 1년에도 남은 빙산이 que에 들어간다.

그리고 'year'가 pop되었을 때, que 안에는 1년도에도 남아있는 빙산의 좌표만 들어있다.

즉 que가 위에서 정의한 cutcheck의 인풋 ice가 될 수 있다.

year가 pop되면 cutcheck(que)를 실행하여 1년도에 빙산이 cut되었는지 T/F를 받는다.

True라면 -year를 출력(year가 음수이므로)하고 종료한다. False라면 year를 -1하고 'year'를 다시 que에 넣는다.

이렇게 'year'가 항상 que에서 그해 빙산의 좌표 뒤에 있도록 관리하면 하나의 while문 안에서 빙산이 녹고 분리됐는지 확인하는 것의 반복이 가능하다.

 

line 56 ~ 58

만약 빙산이 분리되지 않고 다 녹는다면 que에는 'year'만이 남아 계속 자신을 추가하는 무한루프가 될 것이다.

그러므로 'year'가 pop된 que가 비어있다면 (= 내년에 빙산이 하나도 없다면) 0을 출력하고 종료한다.