[백준] 2573번 - 빙산 (파이썬)

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

# 빙산
from collections import deque
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
arr = []
ice = []
melt = []
for i in range(N):
    arr.append(list(map(int, input().split())))
    for j in range(M):
        if arr[i][j] != 0:
            ice.append((i, j))
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def melt_check():
    for x, y in ice:
        if arr[x][y] != 0:
            zero = 0
            for k in range(4):
                nx = x + dx[k]
                ny = y + dy[k]
                if 0 <= nx < N and 0 <= ny < M:
                    if arr[nx][ny] == 0:
                        zero += 1
            if zero != 0:
                melt.append((x, y, zero))


def melt_ice():
    while melt:
        x, y, how = melt.pop()
        arr[x][y] -= how
        if arr[x][y] < 0:
            arr[x][y] = 0


def check():
    global year
    num = 0
    visited = [[False]*M for _ in range(N)]
    melted = 0
    for x, y in ice:
        if arr[x][y] != 0 and not visited[x][y]:
            bfs(x, y, visited)
            num += 1
            # 두 덩어리 이상이면 return True
            if num > 1:
                return True
        # 녹은 개수 빙하 수 체크
        if arr[x][y] == 0:
            melted += 1
    # 다 녹았으면 0 출력, return True
    if melted == len(ice):
        year = 0
        return True
    # 그 외엔 return False
    return False


def bfs(a, b, visited):
    q = deque()
    q.append((a, b))
    visited[a][b] = True
    while q:
        x, y = q.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] and arr[nx][ny] != 0:
                visited[nx][ny] = True
                q.append((nx, ny))


year = 0
while True:
    if check():
        break
    melt_check()
    melt_ice()
    year += 1

print(year)

 

BFS

1. 입력을 받으면서 빙산의 위치를 ice에 append

2. while True 안에서 (check함수 : 두 덩어리 이상이거나, 다 녹았으면(year = 0) break)

• 녹을 얼음들을 기록 (melt_check 함수) : 상하좌우를 확인해서 0의 개수만 큼 좌표와 그 수를 melt에 append
• 얼음 녹이기 (melt 함수) : melt가 빌 때까지 pop을 하면서 해당 얼음 녹이기 (단, 0이하이면 0으로)
• year += 1

3. year 출력

 

 

얼음을 녹이면서 다음 녹을 얼음을 찾으면 주변의 물의 영역 수(0)가 달라질 수가 있다

원래 얼음인데 녹아서 0으로 변하면 다음 얼음에 영향을 줄 수 있음

그래서 melt에 받아놓고 한번에 처리했다.