[백준] 2573 : 빙산 (Python)

정답코드

import sys
input = sys.stdin.readline

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

dx=[1,0,-1,0]
dy=[0,1,0,-1]
    
from collections import deque
def bfs(x, y): # 이어진 빙산 모두 0으로 만들기
    q = deque([(x,y)])
    ans = 0
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if -1 < nx and nx < N and -1 < ny and ny < M and tmp_m[nx][ny]:
                tmp_m[nx][ny] = 0
                q.append((nx,ny))
                ans += 1
    return ans
                
total_ice = 0
for a in m:
    for b in a:
        if b:
            total_ice += 1
year = 0
tmp_m = [[x for x in e] for e in m]
while total_ice:
    for x in range(N):
        for y in range(M):
            if tmp_m[x][y] and total_ice != bfs(x,y):
                print(year)
                exit()
    tmp_m = [[x for x in e] for e in m]
    for x in range(N):
        for y in range(M):
            if m[x][y]:
                 for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if -1 < nx and nx < N and -1 < ny and ny < M:
                        if not m[nx][ny] and tmp_m[x][y]:
                            tmp_m[x][y] -= 1
                            if tmp_m[x][y] == 0:
                                total_ice -= 1
    m = [[x for x in e] for e in tmp_m]
    year += 1
print(0)

💡아이디어

빙하 상태를 tmp_m에 복사하여 시간이 지나 빙하를 녹이거나, bfs로 빙하의 크기를 return한다.
total_ice와 bfs함수의 return값이 동일하면 year를 print한다.

Test Case

나를 구제해준 Test Case..

7 9
0 0 0 0 0 0 0 0 0
0 9 5 5 5 5 5 9 0
0 5 9 5 5 5 9 5 0
0 5 5 9 1 9 5 5 0
0 5 9 5 5 5 9 5 0
0 9 5 5 5 5 5 9 0
0 0 0 0 0 0 0 0 0
answer : 11
output : 0

❗❗❗빙하 최대 높이가 10일 뿐이지 빙산이 전부 녹는데에는 10년보다 오래 걸릴 수도 있다.❗❗❗
감사합니다. 백준 질문 게시판 출처