[Python] 백준 #2573 빙산

📚문제: #2573 빙산(Gold 4)

지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.

빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 따라서 그림 1의 빙산은 일년후에 그림 2와 같이 변형된다.

그림 3은 그림 1의 빙산이 2년 후에 변한 모습을 보여준다. 2차원 배열에서 동서남북 방향으로 붙어있는 칸들은 서로 연결되어 있다고 말한다. 따라서 그림 2의 빙산은 한 덩어리이지만, 그림 3의 빙산은 세 덩어리로 분리되어 있다.

한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.

입력

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.

출력

첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.

예제 모음

(입력)
5 7
0 0 0 0 0 0 0
0 2 4 5 3 0 0
0 3 0 2 5 2 0
0 7 6 2 4 0 0
0 0 0 0 0 0 0

(출력)
2

아이디어 및 구현

• 빙산을 녹이는 BFS 알고리즘
  • 인접지역이 바다면 방문처리 후 큐에 추가한다.
  • 인접지역이 높이 2이상의 빙산이면 1만큼 녹인다. 큐에는 추가하지 않는다.
  • 인접지역이 높이 1의 빙산이면 방문처리한다. 큐에는 추가하지 않는다.
  • 이미 방문된 지점은 Skip한다.
  • 빙산안에 갇혀있는 바닷물이 있는지 찾는다. 빙산이 해당 바닷물에도 영향을 받도록 코드를 작성한다.
  • 몇 덩어리로 구분되는지 파악한다.

# BFS_Melt Algorithm
def BFS_Melt(start):

    # 시작지점
    start_r, start_c = start

    # 4방향
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]

    # 시작지점 방문처리
    graph[start_r][start_c] = 'v'

    # 큐 선언
    queue = deque([start])

    # 큐가 빌 때까지 반복
    while queue:

        cur_r, cur_c = queue.popleft()

        # 꺼낸 지점 방문처리
        graph[cur_r][cur_c] = 'v'

        # 4방향 탐색
        for i in range(4):

            move_r, move_c = cur_r + dr[i], cur_c + dc[i]

            # 주어진 영역을 벗어나지 않을 때
            if 0 <= move_r <= N-1 and 0 <= move_c <= M-1:

                # 이미 방문된 지점은 skip
                if graph[move_r][move_c] == 'v':

                    continue
                
                # 인접지역이 바다일 때
                elif graph[move_r][move_c] == 0:

                    # 방문처리
                    graph[move_r][move_c] = 'v'

                    # 큐에 추가
                    queue.append([move_r, move_c])
                
                # 녹아 없어질 빙산입니다.
                elif graph[move_r][move_c] == 1:

                    # 방문처리, 큐에는 추가하지 않습니다.
                    graph[move_r][move_c] = 'v'
                
                # 빙산의 높이를 1만큼 낮춥니다. 큐에는 추가하지 않습니다.
                elif graph[move_r][move_c] > 1:

                    graph[move_r][move_c] -= 1
                
    # 빙산안에 갇혀있는 호수가 있는지 찾습니다.
    for i in range(N):

        for j in range(M):

            if graph[i][j] == 0:

                queue.append([i,j])
    
    if len(queue) > 0:
        # 큐가 빌 때까지 반복
        while queue:

            cur_r, cur_c = queue.popleft()

            graph[cur_r][cur_c] = 'v'

            # 4방향 탐색
            for i in range(4):

                move_r, move_c = cur_r + dr[i], cur_c + dc[i]

                # 주어진 영역을 벗어나지 않을 때
                if 0 <= move_r <= N-1 and 0 <= move_c <= M-1:

                    # 이미 방문된 지점은 skip
                    if graph[move_r][move_c] == 'v':

                        continue
                    
                    # 인접지역이 바다일 때
                    elif graph[move_r][move_c] == 0:

                        # 방문처리
                        graph[move_r][move_c] = 'v'

                        # 큐에 추가
                        queue.append([move_r, move_c])
                    
                    # 녹아 없어질 빙산입니다.
                    elif graph[move_r][move_c] == 1:

                        # 방문처리, 큐에는 추가하지 않습니다.
                        graph[move_r][move_c] = 'v'
                    
                    # 빙산의 높이를 1만큼 낮춥니다. 큐에는 추가하지 않습니다.
                    elif graph[move_r][move_c] > 1:

                        graph[move_r][move_c] -= 1
    
    # 그래프 복사
    temp = deepcopy(graph)

    # 몇 덩어리로 구성되어있는지 살펴봅니다.
    cnt = 0

    for i in range(N):

        for j in range(M):

            if type(temp[i][j]) == int:

                cnt += BFS_count([i,j], temp)

    # 원복
    for i in range(N):

        for j in range(M):

            if graph[i][j] == 'v':

                graph[i][j] = 0
    
    # 덩어리 개수를 리턴합니다.
    return cnt

• 빙산의 덩어리를 세는 BFS 알고리즘
  • 붙어있는 빙산조각들을 한 덩어리로 세고 1을 리턴한다.

# BFS_count Algorithm
def BFS_count(start, area):

    # 시작 지점
    start_r, start_c = start

    # 4방향
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]

    # 시작지점 방문처리
    area[start_r][start_c] = 'v'

    # 큐 선언
    queue = deque([start])

    # 큐가 빌 때까지 반복
    while queue:

        cur_r, cur_c = queue.popleft()

        # 4방향 탐색
        for i in range(4):

            move_r, move_c = cur_r + dr[i], cur_c + dc[i]

            # 영역을 벗어나지 않으면서
            if 0 <= move_r <= N-1 and 0 <= move_c <= M-1:

                # 방문하지 않은 지점일 때
                if area[move_r][move_c] != 'v':
                    
                    # 방문처리
                    area[move_r][move_c] = 'v'
                    
                    # 큐에 추가
                    queue.append([move_r, move_c])
                
                # 필요없는 지점일 때
                else:
                    
                    continue
    
    # 하나의 덩어리 탐색 완료, 1 리턴
    return 1

전체 코드

import sys
from collections import deque
from copy import deepcopy

# BFS_count Algorithm
def BFS_count(start, area):

    # 시작 지점
    start_r, start_c = start

    # 4방향
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]

    # 시작지점 방문처리
    area[start_r][start_c] = 'v'

    # 큐 선언
    queue = deque([start])

    # 큐가 빌 때까지 반복
    while queue:

        cur_r, cur_c = queue.popleft()

        # 4방향 탐색
        for i in range(4):

            move_r, move_c = cur_r + dr[i], cur_c + dc[i]

            # 영역을 벗어나지 않으면서
            if 0 <= move_r <= N-1 and 0 <= move_c <= M-1:

                # 방문하지 않은 지점일 때
                if area[move_r][move_c] != 'v':
                    
                    # 방문처리
                    area[move_r][move_c] = 'v'
                    
                    # 큐에 추가
                    queue.append([move_r, move_c])
                
                # 필요없는 지점일 때
                else:
                    
                    continue
    
    # 하나의 덩어리 탐색 완료, 1 리턴
    return 1

# BFS_Melt Algorithm
def BFS_Melt(start):

    # 시작지점
    start_r, start_c = start

    # 4방향
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]

    # 시작지점 방문처리
    graph[start_r][start_c] = 'v'

    # 큐 선언
    queue = deque([start])

    # 큐가 빌 때까지 반복
    while queue:

        cur_r, cur_c = queue.popleft()

        # 꺼낸 지점 방문처리
        graph[cur_r][cur_c] = 'v'

        # 4방향 탐색
        for i in range(4):

            move_r, move_c = cur_r + dr[i], cur_c + dc[i]

            # 주어진 영역을 벗어나지 않을 때
            if 0 <= move_r <= N-1 and 0 <= move_c <= M-1:

                # 이미 방문된 지점은 skip
                if graph[move_r][move_c] == 'v':

                    continue
                
                # 인접지역이 바다일 때
                elif graph[move_r][move_c] == 0:

                    # 방문처리
                    graph[move_r][move_c] = 'v'

                    # 큐에 추가
                    queue.append([move_r, move_c])
                
                # 녹아 없어질 빙산입니다.
                elif graph[move_r][move_c] == 1:

                    # 방문처리, 큐에는 추가하지 않습니다.
                    graph[move_r][move_c] = 'v'
                
                # 빙산의 높이를 1만큼 낮춥니다. 큐에는 추가하지 않습니다.
                elif graph[move_r][move_c] > 1:

                    graph[move_r][move_c] -= 1
                
    # 빙산안에 갇혀있는 호수가 있는지 찾습니다.
    for i in range(N):

        for j in range(M):

            if graph[i][j] == 0:

                queue.append([i,j])
    
    if len(queue) > 0:
        # 큐가 빌 때까지 반복
        while queue:

            cur_r, cur_c = queue.popleft()

            graph[cur_r][cur_c] = 'v'

            # 4방향 탐색
            for i in range(4):

                move_r, move_c = cur_r + dr[i], cur_c + dc[i]

                # 주어진 영역을 벗어나지 않을 때
                if 0 <= move_r <= N-1 and 0 <= move_c <= M-1:

                    # 이미 방문된 지점은 skip
                    if graph[move_r][move_c] == 'v':

                        continue
                    
                    # 인접지역이 바다일 때
                    elif graph[move_r][move_c] == 0:

                        # 방문처리
                        graph[move_r][move_c] = 'v'

                        # 큐에 추가
                        queue.append([move_r, move_c])
                    
                    # 녹아 없어질 빙산입니다.
                    elif graph[move_r][move_c] == 1:

                        # 방문처리, 큐에는 추가하지 않습니다.
                        graph[move_r][move_c] = 'v'
                    
                    # 빙산의 높이를 1만큼 낮춥니다. 큐에는 추가하지 않습니다.
                    elif graph[move_r][move_c] > 1:

                        graph[move_r][move_c] -= 1
    
    # 그래프 복사
    temp = deepcopy(graph)

    # 몇 덩어리로 구성되어있는지 살펴봅니다.
    cnt = 0

    for i in range(N):

        for j in range(M):

            if type(temp[i][j]) == int:

                cnt += BFS_count([i,j], temp)

    # 원복
    for i in range(N):

        for j in range(M):

            if graph[i][j] == 'v':

                graph[i][j] = 0
    
    # 덩어리 개수를 리턴합니다.
    return cnt

# N, M이 주어진다.
N, M = map(int, sys.stdin.readline().split())

# 그래프 초기화
graph = []

# 그래프 반영
for _ in range(N):

    graph.append(list(map(int, sys.stdin.readline().split())))

# 시작지점
s = [0,0]

# 빙산이 분리되는 최초의 시간
time = 0

# 빙산을 계속 녹입니다.
while True:

    cnt = BFS_Melt(s)

    time += 1

    if cnt == 1:

        continue

    # 덩어리가 2개 이상이라면 종료
    elif cnt == 0 or cnt > 1:

        break

# 0 출력
if cnt == 0:
    
    print(0)

else:

    print(time)

TIL

BFS 알고리즘 작성 시 큐에 바다영역을 계속 추가하면서 바다의 인접 영역이 빙산일 때 녹이는 과정을 반복하였다. 이 방법으로 작성하면 코드가 다소 지저분해지는 경향이 있다. 다시 이 문제를 풀 때는 각 빙산 영역의 상,하,좌,우 인접영역에 위치한 바다의 개수만큼 빙산을 녹이는 과정으로 작성해야겠다.