[백준] 2573 빙산 (Python)

🔗 문제 링크

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

💻 코드

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

n,m = map(int,input().split())

def isvalid(x,y):
    return 0 <= x < n and 0 <= y < m 
    
graph = [list(map(int,input().split())) for _ in range(n)]
year = 0

def bfs(i,j):
    dir = [(0,1), (0,-1),(1,0), (-1,0)]
    dq = deque([(i,j)])
    visited[i][j] = 1

    while dq:
        cx,cy = dq.popleft()

        for dx,dy in dir:
            nx,ny = dx+cx,dy+cy
            if isvalid(nx,ny) and not visited[nx][ny]:
                if graph[nx][ny] > 0:
                    visited[nx][ny] = 1
                    dq.append((nx,ny))
                else:
                    cnt[cx][cy] += 1
    return 1

while True:
    result = []
    visited = [[0] * m for _ in range(n)]
    cnt = [[0] * m for _ in range(n)]

    for i in range(n):
        for j in range(m):
            if graph[i][j] > 0 and not visited[i][j]:
                result.append(bfs(i,j))

    for i in range(n):
        for j in range(m):
            graph[i][j] -= cnt[i][j]
            if graph[i][j] < 0:
                graph[i][j] = 0

    if len(result) == 0 or len(result) >=2:
        break 
    year += 1
print(year) if len(result) >= 2 else print(0)

🧩 풀이

• 처음에는 시간초과가 남 -> 아무래도 매번 BFS를 돌리면 안되고 좌표를 한 번에 처리해야되는 것 같다. (왜 빙산은 하나로 다 이어졌는데 매 지점을 다 세려고 했을까?)

• 빙산이 두 덩어리 이상으로 처음 분리되는 시점을 찾아야한다.

• BFS로 빙산 덩어리 개수를 세서, 하나면 계속 녹이고

  • 2개로 나뉘면 그때의 Year를 출력