[백준] 2573번. 빙산

[백준] 2573번. 빙산 바로가기

아이디어

• 재귀로 풀기 싫어서 while문 돌려서 했다.
• 그냥 문제에서 구현하라는 대로 했다.

0. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.
1. 빙산 덩어리 계산하는 거랑 각 빙산이 바다에 맞닿아있는 부분 계산 구하는 메서드가 중복될 것 같아서 하나로 합쳤다.
2. 빙산 녹이는 부분은 그냥 단순하게 반복문 돌려서 했다.
3. 빙산 덩어리가 2개 이상될 때 까지 1~2 반복
   3-1. 만약에 덩어리가 분리되지 않고 다 녹으면 0 출력 -> 문제를 잘 읽자... 제발

시간 복잡도

• O(n * m)

코드

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

# 빙산 개수 체크
def check_iceburg(n, m, visited):
    global cnt
    for x in range(1, n - 1):
        for y in range(1, m - 1):
            if sea[x][y] != 0 and visited[x][y] != 1:
                count_iceberg(x, y)
                cnt += 1

# 빙산 개수 + 바다와 닿은 면 개수 체크
def count_iceberg(x, y):
    global iceburg_list
    q.append((x, y))
    visited[x][y] = 1

    while q:
        x, y = q.popleft()
        melting_cnt = 0    # 바다에 닿은 면 개수

        # 인접한 면 체크
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                # 빙산이면 q에 담아주기
                if sea[nx][ny] != 0:
                    q.append((nx, ny))
                    visited[nx][ny] = 1
                # 바다(0)이면 닿는 면 체크
                else:
                    melting_cnt += 1
        
        # 빙산 리스트에 담기
        iceburg_list.append((x, y, melting_cnt)) 


# 녹을 수 있는 면 체크
def melt(iceburg_list):
    # 빙산 리스트를 돌면서 바다가 닿은 면 만큼 녹여주기
    while iceburg_list:
        x, y, cnt = iceburg_list.popleft()

        sea[x][y] -= cnt

        if sea[x][y] < 0:
            sea[x][y] = 0


n, m = map(int, input().split())
sea = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
year = 0
q = deque([])

while True:
    # 1년이 지나면 초기화 해줘야함
    cnt = 0           # 빙산 개수
    iceburg_list = deque([]) # 빙산 리스트 담을 리스트
    visited = [[0] * m for _ in range(n)] # 카운트 하기전에 매번 초기화

    # 빙산 개수 체크하기
    check_iceburg(n, m, visited)

    # 빙산이 2개 이상되면 종료
    if cnt >= 2:
        print(year)
        break

    # 그냥 다 녹았으면 0 출력
    if cnt == 0:
        print(0)
        break
    
    # 녹이기
    melt(iceburg_list)

    # 시간 더해주기
    year += 1