[Python] 백준 2573. 빙산

 

문제 링크

 

 

풀이

빙산을 녹이는 함수를 만들어서 빙산이 녹을 때마다 시간이 1년 지나게 하였다.

모든 좌표에서 bfs 탐색해서 분리된 것들의 개수를 구하고

분리된 것이 2개 이상이면 걸린 시간을 출력하고 종료

빙산이 다 녹았으면 0을 출력하고 종료

 

 

코드

'''
bfs 탐색 한번
융해작업 1번
융해작업이 끝나면 time += 1
빙산의 부분은 0미만으로는 안떨어짐
분리되면 종료
빙산이 다 녹아도 종료
'''
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

# 모든 좌표를 bfs하여 연결된 것의 개수 확인
# 탐색하여 분리되면 종료이고, 빙산이 다 녹아도 종료이다.
def bfs(x,y):
    q = deque()
    q.append((x,y))
    visited[x][y] = 1
    while q:
        i, j = q.popleft()
        for k in [(0,1), (1,0), (0,-1), (-1,0)]:
            ni = i + k[0]
            nj = j + k[1]
            # 주변에 빙산의 부분이 있으면
            if 0 <= ni < n and 0 <= nj < m and arr[ni][nj] != 0 and not visited[ni][nj]:
                q.append((ni,nj))
                visited[ni][nj] = 1
    return 1

# 멜팅 작업
def melting():
    ls = []
    for i in range(n):
        for j in range(m):
            # 빙산에서 델타탐색하여 뺄값을 모두 저장해두고 한방에 터트리기
            melt = 0
            if arr[i][j] != 0:
                for k in [(0,1), (1,0), (0,-1), (-1,0)]:
                    ni = i + k[0]
                    nj = j + k[1]
                    if 0 <= ni < n and 0 <= nj < m and arr[ni][nj] == 0:
                        melt += 1
                ls.append((i,j,melt))
    for i in ls:
        if arr[i[0]][i[1]] <= i[2]:
            arr[i[0]][i[1]] = 0
        else:
            arr[i[0]][i[1]] -= i[2]
time = 0
while 1:
    visited = [[0]*m for _ in range(n)]
    res = 0
    for i in range(n):
        for j in range(m):
            if not visited[i][j] and arr[i][j] != 0:
                res += bfs(i,j)
                if res >= 2:
                    break
    # 빙산이 두 덩어리 이상으로 분리 혹은 다 녹음
    if res >= 2:
        print(time)
        break
    elif res == 0:
        print(0)
        break
    melting()
    time += 1

pypy3으로 제출했습니다