🦊 빙산

1. 문제 링크

2573번: 빙산

2. 코드

pypy3 242500kb 2136ms

import sys
sys.setrecursionlimit(10005)

N, M = map(int, input().split())

T = 0
MAP = []
ICEBURG = []
VISIT_MAP = []
for i in range(N):
    MAP.append(list(map(int, sys.stdin.readline().split())))
    
    for j in range(M):
        if MAP[i][j] != 0:
            ICEBURG.append([j, i, MAP[i][j]]) # (x, y, size) 저장
    
# 방문맵 초기화
def init():
    global VISIT_MAP
    VISIT_MAP = [[0] * M for i in range(N)]
    
def dfs(x, y):
    global MAP, VISIT_MAP, N, M
    delta = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    VISIT_MAP[y][x] = 0
    for dx, dy in delta:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < M and 0 <= ny < N and VISIT_MAP[ny][nx] == 1:
            dfs(nx, ny)

# 방문맵 검사
def countIceburg():
    global MAP, VISIT_MAP, N, M, T
    init()
    count = 0
    
    # 빙산 있는 곳을 체크
    for i in range(N):
        for j in range(M):
            if MAP[i][j] > 0:
                VISIT_MAP[i][j] = 1
    for i in range(N):
        for j in range(M):                
            if VISIT_MAP[i][j] == 1:
                dfs(j, i)
                count += 1

    # 두개 이상의 빙산으로 나뉘어짐
    return count

while countIceburg() == 1:
    T += 1
    delta = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    melt = []
    for x, y, size in ICEBURG:
        if size == 0:
            continue
        count = 0
        for dx, dy in delta:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < M and 0 <= ny < N and MAP[ny][nx] == 0:
                count += 1
        melt.append([x, y, max(0, size - count)])
    
    for x, y, size in melt:
        MAP[y][x] = size

        
    ICEBURG = melt.copy()

if countIceburg() == 0:
    print(0)
else:
    print(T)

• 해설

  빙산의 좌표를 저장

  해당 빙산의 다음 좌표를 기록

  맨 마지막에 반영시킴

  dfs 를 통해 빙산의 개수 구해서 1이 아니면 루프 종료

  0이면 빙산이 모두 녹아버림

  2 이상이면 빙산이 분리되어짐