빙산의 높이가 숫자로 주어지고 1년마다 둘러싸인 0(바다)의 숫자만큼 빙산의 높이가 낮아지는데
빙산이 두 덩이 이상이 되는 시점의 햇수를 출력하는 문제다.
테두리는 0으로 채워져있기 때문에 1 ~ N-1, 1 ~ M-1을 반복문을 돌리면서
둘러싸인 0의 개수를 카운트 후 배열에 저장,
이후 반복문을 돌리면서 빙산 높이에서 둘러싼 0 개수만큼을 빼준 다음
반복문과 BFS를 통해 빙산 덩어리 개수를 세주고 cnt를 갱신,
cnt가 1을 초과하는 시점에 year를 리턴해주고
반복문을 돌았는데 cnt가 0이 되었다면 (빙산이 덩어리로 분리되지 않고 다 녹았다면)
0을 리턴한다.
요약
코드
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)