[백준 Python] 2573번 빙산

백준 파이썬 2573번 빙산

Gold 4

 

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

 

import sys
from collections import deque
input = sys.stdin.readline
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
def check_ice(x, y):
    visited = [[False]*m for _ in range(n)]
    q = deque()
    q.append((x, y))
    tmp_cnt = 0
    while q:
        x, y = q.popleft()
        for tx, ty in move:
            dx = x+tx
            dy = y+ty
            if 0 <= dx < n and 0<= dy < m and not visited[dx][dy] and lst[dx][dy] != 0:
                visited[dx][dy] = True
                q.append((dx, dy))
                tmp_cnt += 1
    return tmp_cnt
n, m = map(int, input().split())
lst = []
que = deque()
for i in range(n):
    tmp = list(map(int, input().split()))
    lst.append(tmp)
    for j in range(m):
        if tmp[j] != 0:
            que.append((i, j))
time = 0
while True:
    if len(que) != 0:
        x, y = que[0]
        if check_ice(x, y) != len(que):
            print(time)
            exit()
    else:
        print(0)
        exit()
    t1_que = que.copy()
    t2_que = deque()
    oceans = deque()
    while t1_que:
        i, j = t1_que.popleft()
        ocean = 0
        for ti, tj in move:
            di = i+ti
            dj = j+tj
            if lst[di][dj] == 0:
                ocean += 1
        if lst[i][j] > ocean:
            t2_que.append((i, j))
        oceans.append((i, j, ocean))
    while oceans:
        i, j, ocean = oceans.popleft()
        lst[i][j] -= ocean
        if lst[i][j] < 0:
            lst[i][j] = 0
    que = t2_que.copy()
    time += 1

 

1. check_ice() 빙산이 두 덩어리 이상으로 나뉘는지 확인하는 함수

2. t1_que() : que의 값을 임시로 갖는 deque(). t1_que를 이용해 빙산의 줄어들 높이를 구한다.

3. t2_que() : 남아있는 빙산의 좌표를 저장하는 deque()