[WEEK03] 21일차. 빙산

kozi·2023년 3월 19일
0

SW사관학교 정글

목록 보기
17/33

백준 2573 빙산

빙산의 높이가 숫자로 주어지고 1년마다 둘러싸인 0(바다)의 숫자만큼 빙산의 높이가 낮아지는데
빙산이 두 덩이 이상이 되는 시점의 햇수를 출력하는 문제다.

테두리는 0으로 채워져있기 때문에 1 ~ N-1, 1 ~ M-1을 반복문을 돌리면서
둘러싸인 0의 개수를 카운트 후 배열에 저장,
이후 반복문을 돌리면서 빙산 높이에서 둘러싼 0 개수만큼을 빼준 다음
반복문과 BFS를 통해 빙산 덩어리 개수를 세주고 cnt를 갱신,

cnt가 1을 초과하는 시점에 year를 리턴해주고
반복문을 돌았는데 cnt가 0이 되었다면 (빙산이 덩어리로 분리되지 않고 다 녹았다면)
0을 리턴한다.

요약

  1. 둘러싼 0 개수 셈
  2. 빙산 높이 낮춤
  3. 덩어리 개수 셈

코드

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

N, M = map(int, input().split())

def bfs(i, j, visited):
    q = deque()
    q.append((i,j))
    visited[i][j] = 1

    while q:
        ci, cj = q.popleft()
        for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            ni, nj = ci + di, cj + dj
            if not visited[ni][nj] and ice[ni][nj]:
                q.append((ni,nj))
                visited[ni][nj] = 1

def solve():
    for year in range(1, 90000):
        melting = [[0] * M for _ in range(N)]
        # 0 개수 세기
        for i in range(1, N-1):
            for j in range(1, M-1):
                if not ice[i][j]:
                    continue
                for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                    ni, nj = i + di, j + dj
                    if not ice[ni][nj]:
                        melting[i][j] += 1
        # 높이 낮추기
        for i in range(1, N-1):
            for j in range(1, M-1):
                if melting[i][j] > 0:
                    ice[i][j] = max(0, ice[i][j] - melting[i][j])
        # 덩어리 세기
        visited = [[0] * M for _ in range(N)]
        cnt = 0
        for i in range(1, N-1):
            for j in range(1, M-1):
                if not visited[i][j] and ice[i][j]:
                    bfs(i, j, visited)
                    cnt += 1
                    if cnt > 1:
                        return year
        if cnt == 0:
            return 0
    return -1

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

ans = solve()
print(ans)
profile
어제보다 잘하고 싶은 개발자 Kozi 입니다.

0개의 댓글