풀이
시간이 지날 때 마다 빙산이 녹고 빙산이 2 조각 이상 분리될 경우 몇 년이 걸리는지 계산하는 문제이다.
1년이 지날 때 마다 빙산이 녹는 기능은 “미세먼지 안녕!” 문제.
빙산의 조각을 세는 기능은 “단지번호붙이기” 문제.
”단지번호붙이기” 문제와 “미세먼지 안녕!” 문제를 합쳐놓은 문제같다.
while문을 활용해 모든 빙산이 녹거나 빙산이 2 조각 이상으로 분리될 때 까지 위 기능을 반복시킨다.
visited 와 new 2 차원 배열을 초기화 해주면서 1년 후 빙산이 녹았을 때 정보를 new 에 저장해주고,
이 new 를 bfs 에 집어넣어 visited 를 통해 방문처리를 해준다.
bfs 가 한 번 실행될 때 마다 빙산 한 조각이 있다는 얘기기 때문에 이에 맞춰서 piece 변수를 수정해주고,
2 조각 이상일 경우 종료, 아닐 경우 반복하면된다.
소스코드
# 빙산
from collections import deque
import sys
input = sys.stdin.readline
def bfs(i, j):
q = deque()
q.append([i, j])
visited[i][j] = 1
while q:
x, y = q.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx < n and 0 <= ny < m: # 범위 내일 때
if new[nx][ny] != 0 and visited[nx][ny] == 0: # 빙산이 이어져 있으며 방문하지 않았을 경우
q.append([nx, ny])
visited[nx][ny] = 1 # 방문 처리
return
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
years = 1
while True:
# 빙산이 다 녹을 때 까지 분리되지 않을 경우
zero = 0
for g in graph:
zero += sum(g)
if zero == 0:
print(0)
break
# 초기화
visited = [[0] * m for _ in range(n)]
new = [[0] * m for _ in range(n)]
piece = 0
# 지구 온난화
for i in range(n):
for j in range(m):
if graph[i][j] != 0:
temp = graph[i][j]
for k in range(4):
nx = i + dx[k]
ny = j + dy[k]
if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:
temp -= 1
if temp > 0:
new[i][j] = temp
# 빙산이 몇 조각인지 확인
for i in range(n):
for j in range(m):
if new[i][j] != 0 and visited[i][j] == 0:
bfs(i, j)
piece += 1
# 빙산이 분리될 경우
if piece > 1:
print(years)
break
# 1년 후 빙산정보 업데이트
years += 1
graph = new