파이썬 | 백준 | 2573 | 빙산

solution

1. dir4(x, y): 주변의 0 카운트하여 개수만큼 빙산을 녹임. 다 녹으면 -1로 만듦.

(0으로 바로 만들면 인접한 빙산을 dir4()이용해 녹일 때 0 개수가 같이 카운트 되므로 일단 -1로 만들고 큐에 좌표 저장)

2. bfs_all() : 빙산의 덩어리를 세는 함수

 

* PyPy3로 제출

# 2573, 빙산
import sys
from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def dir4(x, y):
    zero = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < M:
            if ice[nx][ny] == 0:
                zero += 1
    if ice[x][y] <= zero:
        ice[x][y] = -1
        melted.append((x, y))
    else:
        ice[x][y] -= zero


def bfs(x, y):
    visited[x][y] = 1
    q = deque()
    q.append((x, y))

    while q:
        a, b = q.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]

            if 0 <= nx < N and 0 <= ny < M:
                if visited[nx][ny] == 0 and ice[nx][ny] != 0:
                    visited[nx][ny] = visited[a][b] + 1
                    q.append((nx, ny))


# 몇 덩어린지 세기 위한 bfs
def bfs_all():
    cnt = 0
    for i in range(N):
        for j in range(M):
            if ice[i][j] != 0 and visited[i][j] == 0:
                bfs(i, j)
                cnt += 1
    return cnt

N, M = map(int, sys.stdin.readline().split())
ice = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
visited = [[0] * M for _ in range(N)]
melted = deque()
year = 0

tmp = bfs_all()
while tmp == 1:

    for i in range(N):
        for j in range(M):
            if ice[i][j] != 0:
                dir4(i, j)

    while melted:
        r, c = melted.popleft()
        ice[r][c] = 0

    visited = [[0] * M for _ in range(N)]
    year += 1
    tmp = bfs_all()

if tmp == 0:
    year = 0

print(year)

 

문제 출처 www.acmicpc.net/problem/2573

2573번: 빙산