[python] 백준 2573 빙산

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

2573번: 빙산

 

문제 해결

• 빙산의 녹는 것을 계산한 다음 바다로 인해 하나였던 빙산이 두 개 이상으로 분리되는데 걸린 시간을 구하는 문제
• bfs를 통해 빙산의 개수를 구할 수 있다.

 

CODE

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

def bfs(x,y):
    que = deque()
    que.append((x,y))
    visited[x][y] = 1
    sealist = []
    while que:
        a, b = que.popleft()
        sea = 0
        for i in range(4):
            new_a = a + dx[i]
            new_b = b + dy[i]
            if 0<=new_a<n and 0<=new_b<m:
                if not graph[new_a][new_b]:
                    sea += 1
                elif graph[new_a][new_b] and not visited[new_a][new_b]:
                    que.append((new_a, new_b))
                    visited[new_a][new_b] = 1
        if sea>0:
            sealist.append((a,b,sea))
    for r, c, sea in sealist:
        graph[r][c] = max(0, graph[r][c]-sea)
    return 1

n, m = map(int, input().split())
graph = [list(map(int,input().split())) for _ in range(n)]
ice = []
for i in range(n):
    for j in range(m):
        if graph[i][j]>0:
            ice.append((i,j))
dx = [-1,1,0,0]
dy = [0,0,-1,1]
year = 0

while ice:
    visited = [[0]*m for _ in range(n)]
    delList = [] # 없어진 빙하지역
    group = 0
    for i, j in ice:
        if graph[i][j] and not visited[i][j]:
            group += bfs(i,j)
        if graph[i][j]==0:
            delList.append((i,j))
    if group>1:
        print(year)
        break
    ice = sorted(list((set(ice)-set(delList))))
    year += 1
if group <2:
    print(0)