백준 2573 빙산

과정

1. 빙산이 녹음 (단순 구현)
   • 기존 2차원 배열에 반영하면, 옆 칸 결과에 영향 받을 수 있으므로 새로운 2차원 배열을 만들어서 녹은 결과를 저장.
2. 그 때 빙산 덩어리 개수 구함 (BFS 또는 DFS)
   • 빙산 덩어리 개수가 2 이상이 되면 해당 년도 출력
     • 이상 으로 하는 이유는 녹았을 때 3 이상의 덩어리가 될 수 있기 때문
   • 0이 되면 0 출력

• 양 모서리가 0으로 주어진다고 했으니 빙산이 녹을 때 인덱스 확인은 안해도 됬을 것 같다. 연산 횟수 줄일 수 있었을 것이라 생각.

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

N, M = map(int, input().split())
map_lst = [list(map(int, input().split())) for _ in range(N)]

# 1년이 지나면
# 1. 빙산이 녹음
def melt(original_lst):
    # 0이 아니면, 사방에 0 개수를 확인하고, new_lst에 반영된 값을 추가
    new_lst = [[0] * M for _ in range(N)]
    for i in range(M):
        for j in range(N):
            if original_lst[j][i] != 0:
                new_value = original_lst[j][i] - check_zero(i, j, original_lst)
                if new_value < 0:
                    new_value = 0
                new_lst[j][i] = new_value

    return new_lst


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


def check_zero(x, y, original_lst):
    cnt = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < M and 0 <= ny < N and original_lst[ny][nx] == 0:
            cnt += 1
    return cnt

# 2. 빙산의 덩어리 개수를 세기 (BFS)
def bfs(original_map):
    cnt = 0
    visited = [[False] * M for _ in range(N)]
    for j in range(N):
        for i in range(M):
            if original_map[j][i] != 0 and not visited[j][i]:
                cnt += 1
                if cnt == 2:
                    return cnt
                queue = deque([(i, j)])
                while queue:
                    a = queue.popleft()
                    x = a[0]
                    y = a[1]
                    for idx in range(4):
                        nx = x + dx[idx]
                        ny = y + dy[idx]
                        if 0 <= nx < M and 0 <= ny < N and original_map[ny][nx] != 0 and not visited[ny][nx]:
                            visited[ny][nx] = True
                            queue.append((nx, ny))
    return cnt

year = 0

while True:
    year += 1
    map_lst = melt(map_lst)
    ice = bfs(map_lst)

    if ice >= 2:
        print(year)
        break
    elif ice == 0:
        print(0)
        break

• 엣지케이스를 나름 여럿 생각하면서 진행했다.