[알고리즘][Python] 백준 2573 빙산73 빙산 문제 풀이

문제 출처 : www.acmicpc.net/problem/2573

2573번: 빙산

---

문제 해석 : 빙산은 물에 접한 면의 수만큼 녹는다. 이때 빙산이 2개의 덩어리로 분리 될 때 까지 걸리는 시간을 구하라.

 

문제 풀이 : 2개의 기능을 구현하면 풀 수 있다.

1. 빙산이 2개로 분리되었는지 검사하는 함수

2. 빙산이 1년이 지날 때마다 녹이는 함수

두 개의 함수 모두 BFS 알고리즘을 통해서 풀 수 있으며 풀이는 아래와 같다.

---

풀이 코드

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

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

def check_answer():
    visited = [[0] * M for _ in range(N)]
    Q = deque()
    count = 1
    for i in range(N):
        for j in range(M):
            if count == 3:
                return True

            if ice[i][j] != 0 and visited[i][j] == 0:
                Q.append([i,j])
                visited[i][j] = count
                while Q:
                    x, y = Q.popleft()
                    for k in range(4):
                        nx, ny = x + dx[k], y + dy[k]
                        if 0 <= nx < N and 0 <= ny < M:
                            if visited[nx][ny] == 0 and ice[nx][ny] != 0:
                                visited[nx][ny] = count
                                Q.append([nx,ny])
                count += 1

    return False

N, M = map(int, input().split())
ice = [list(map(int, input().split())) for _ in range(N)]
time = 0
answer = 0
while True:

    if check_answer():
        answer = time
        break
    if ice.count([0]*M) == N:
        break

    temp = copy.deepcopy(ice)
    for i in range(N):
        for j in range(M):
            if temp[i][j] != 0:
                count = 0
                for k in range(4):
                    nx, ny = i + dx[k], j + dy[k]
                    if 0 <= nx < N and 0 <= ny <M:
                        if ice[nx][ny] == 0:
                            count += 1
                temp[i][j] -= count
                if temp[i][j] < 0:
                    temp[i][j] = 0

    ice = copy.deepcopy(temp)
    time += 1

print(answer)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.