BOJ 2573 - 빙산

풀이

---

시간이 지날 때 마다 빙산이 녹고 빙산이 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

References

---

• BOJ 2573 - 빙산