[BOJ] 백준 2573 빙산 / BFS

이미지를 클릭하면 문제 사이트로 이동합니다.

 

 

💭 문제 이해

한 덩어리의 빙산이 입력으로 주어진다.

매년, 빙산의 사방으로 접한 바다면(0)의 개수만큼 녹아내린다.

해마다 녹아내리다보면 어느 시점에 빙산이 끊어지며 덩어리가 나뉘게 된다.

 

예제 입력의 경우 2년이 지나면(두 번 녹으면) 덩어리가 세 덩어리로 나누어진다.

몇 년이 지나면 빙산이 두 덩어리 이상으로 나누어지는지 계산하는 문제이다.

 

1. 빙산을 녹인다.

2. 너비 우선 탐색을 하며 덩어리 개수를 세본다.

3. 두 덩어리 이상으로 나뉘거나, 더 이상 남은 빙산이 없다면 그 결과를 출력한다.

 

 

❗️여기서 내가 놓쳤던 포인트는 빙산을 현재 기준으로 녹이면 잘못 계산한다는 점이다.

 

무슨 말이냐면,,

 

- 먼저 (1, 1) 위치의 높이 2인 빙산은 왼쪽과 위쪽이 바닷물이므로 1년이 지나면 모두 녹아 0이 된다.

	물
물	2 => 0	4	5	3
	3		2	5	2
	7	6	2	4

- 그 상태에서 그대로 (1, 2) 위치의 높이 4인 빙산을 계산하면 3면이 바다이므로(한반도..?) 1이 된다.

		물
	물	4 => 1	5	3
	3	물	2	5	2
	7	6	2	4

- 그러나 잘 생각해보면 문제 조건은 초기 상태 그대로를 기준으로 하므로 위쪽과 아래쪽이 바다인 -2로 계산하는 것이 맞다.

		물
	2	4 => 2	5	3
	3	물	2	5	2
	7	6	2	4

 

 

그러므로 매년 녹는 빙산을 계산할 때, 현재 상태를 복사해두고(cp_world) 이를 기준으로 빙산의 녹는 양을 계산했다.

 

 

구현 언어: Python

 

from collections import deque
from sys import stdin
import copy


# 빙산의 현재 위치가 얼마나 녹을 지 계산
# 상하좌우 네 방향 중 물이 있는 면의 개수를 찾는다.
def oceans(t_x, t_y):
    ocean_cnt = 0
    for k in range(4):
        nx = t_x + mx[k]
        ny = t_y + my[k]
        # 네 방향 중 바다를 찾으면 +1
        if cp_world[nx][ny] == 0:
            ocean_cnt += 1
    return ocean_cnt


# 너비 우선 탐색을 수행하며 빙산 덩어리의 개수를 찾는다.
def bfs():
    groups = 0    # 덩어리 개수
    queue = deque()
    visited = [[False] * m for _ in range(n)]    # 방문 체크
    
    for a in range(1, n-1):
        for b in range(1, m-1):
            # 이전에 방문한 적 없는 빙산을 찾았을 때 거기에서 덩어리 탐색 시작
            if world[a][b] > 0 and not visited[a][b]:
                groups += 1
                queue.append((a, b))    # 시작점
                visited[a][b] = True
                # BFS 시작
                while queue:
                    x, y = queue.popleft()
                    for c in range(4):
                        nx = x + mx[c]
                        ny = y + my[c]
                        # 범위 안에 있고
                        if 1 <= nx < n-1 and 1 <= ny < m-1:
                            # 방문한 적이 없는 빙산을 찾으면 덩어리에 포함
                            if world[nx][ny] > 0 and not visited[nx][ny]:
                                queue.append((nx, ny))
                                visited[nx][ny] = True
                                
    return groups


n, m = map(int, stdin.readline().rstrip().split())
world = [list(map(int, stdin.readline().rstrip().split())) for _ in range(n)]
# 상 하 좌 우
mx = [-1, 1, 0, 0]
my = [0, 0, -1, 1]
year = 0    # 시간
groups = 0    # 덩어리 개수
ice_exist = False    # 빙산이 존재하는지 체크

# 빙산이 두 덩어리 이상이 되면 종료
while groups < 2:
    ice_exist = False
    cp_world = copy.deepcopy(world)
    # 빙산을 녹인다.(테두리는 항상 물이다.)
    for i in range(1, n-1):
        for j in range(1, m-1):
            # 빙산을 발견하면
            if world[i][j] > 0:
                ice_exist = True
                # 바닷물과 접한 부분의 수만큼 녹는다.
                melt = oceans(i, j)
                if world[i][j] <= melt:
                    world[i][j] = 0
                else:
                    world[i][j] -= melt
    # 빙산이 없었으면 바로 종료
    if not ice_exist:
        break
    # 1년이 증가한다.
    year += 1
    # 빙산을 녹인 후 덩어리 개수를 세본다.
    groups = bfs()
                
# 다 녹일 때까지 덩어리가 분리되지 않는다면 0을 출력한다. 
if not ice_exist and groups < 2:
    print(0)
else:
    print(year)