DFS : 빙산(백준 2573번)

▶ 문제 : https://www.acmicpc.net/problem/2573

2573번: 빙산

##### 문제 #####
# 지구 온난화로 인하여 북극의 빙산이 녹고 있다. 
# 빙산을 2차원 배열에 표시한다고 하자. 
# 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 
# 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 
# 빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 
# 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 
# 일 년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 
# 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 
# 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 
# 한 덩어리의 빙산이 주어질 때, 
# 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 
# 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.

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

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

 

▶ 접근 방법

시간의 흐름에 따라 빙산의 높이가 낮아지는 과정,
낮아지는 과정 후 빙산의 분리 여부를 확인하는 것이 필요했다.
빙산의 분리 여부를 확인하는 과정에서
DFS를 통해 특정 좌표의 빙산과 인접 좌표가 연결되어 있는지 확인했다.

 

▶ 풀이 코드

import sys
sys.setrecursionlimit(100000)


def reduce(current_x, current_y):
    num_of_sea = 0
    for dir_x, dir_y in (-1, 0), (1, 0), (0, -1), (0, 1):
        new_x, new_y = current_x + dir_x, current_y + dir_y
        
        if 0 <= new_x < row and 0 <= new_y < col :
            if iceberg[new_x][new_y] == 0:
                num_of_sea += 1
    
    if num_of_sea != 0 :
        return current_x, current_y, num_of_sea
    else :
        return None

def DFS(current_x, current_y):
    visited[current_x][current_y] = True

    for dir_x, dir_y in (-1, 0), (1, 0), (0, -1), (0, 1):
        new_x, new_y = current_x + dir_x, current_y + dir_y
        
        if 0 <= new_x < row and 0 <= new_y < col :
            if not visited[new_x][new_y] and iceberg[new_x][new_y] != 0:
                DFS(new_x, new_y)


# 빙산의 크기를 row, col로 입력 받는다.
row, col = map(int, sys.stdin.readline().split())

# 빙산의 높이 정보를 list로 만든다.
iceberg = [list(map(int, sys.stdin.readline().split())) for _ in range(row)]

# 빙산이 분리되는 시간을 초기 0으로 초기화한다.
time = 0

while True :
    time += 1

    # 1. 시간이 흐를 때마다 빙산을 줄여주자
    total_reduced = []
    for current_x in range(1, row):
        for current_y in range(1, col):
            # 특정 좌표의 빙산 높이가 0이 아니라면
            if iceberg[current_x][current_y] != 0:
                # 해당 좌표의 빙산을 줄여주는 작업을 진행한다.
                reduced_info = reduce(current_x, current_y)

                # 줄여주는 작업 결과가 있다면 이를 total_reduced에 넣어준다.
                if reduced_info is not None :
                    total_reduced.append(reduced_info)
    
    # total_reduced에는 특정 좌표와 그 좌표와 인접한 바다의 숫자를 담고 있다.
    # 거기서 하나씩 꺼내본다.
    for current_x, current_y, reduced in total_reduced:
        # 만약 현재 좌표의 높이가 줄여주는 양보다 높다면
        if iceberg[current_x][current_y] - reduced > 0:
            # 현재 좌표를 갱신해준다.
            iceberg[current_x][current_y] = iceberg[current_x][current_y] - reduced
        else :
            # 아니라면 현재 좌표의 높이를 0으로 조정한다.
            iceberg[current_x][current_y] = 0

    # 2. 빙산을 줄여줬다면, 줄인 결과 빙산이 분리되는지 확인하자    
    ice = 0
    visited = [[False] * col for _ in range(row)]

    # 빙산의 좌표를 확인하는 과정에서 높이가 0이 아니고, 방문한 적이 없다면
    for current_x in range(1, row):
        for current_y in range(1, col):
            if iceberg[current_x][current_y] != 0 and not visited[current_x][current_y]:
                # 빙산 조각을 늘려준다.
                ice += 1
                # 해당 좌표의 주변 좌표들을 DFS를 통해 확인한다.
                DFS(current_x, current_y)

                # 만약 빙산 조각이 2개로 늘어난다면 멈춘다.
                if ice == 2:
                    break
    
    # 빙산의 조각이 1개 이상이라면 멈춘다.
    if ice > 1:
        break
    

    # 빙산이 다 녹았는데도 분리되지 않는 경우가 있을 수 있다.
    # 이런 경우, 시간을 계속 확인할 필요가 없으므로
    total_sum = 0
    # 리스트로 구성된 빙산을 하나씩 돌면서
    for ice in iceberg :
        # 각 리스트의 합을 구해서 다 더해본다.
        total_sum += sum(ice)
    # 다 더한 값이 만약 0이라면
    if total_sum == 0:
        # time을 0으로 지정하고 멈춘다.
        time = 0
        break

if time :
    print(time)
else :
    print(time)

 

▶ 관련 링크

2021.11.18 - [알고리즘] - DFS(Depth First Search, 깊이 우선 탐색)이란?

2021.11.20 - [알고리즘] - DFS :트리의 부모 찾기(백준 11725번)

2021.11.20 - [알고리즘] - 이분 그래프(Bipartite Graph)란?

2021.11.22 - [알고리즘] - DFS : 이분 그래프(백준 : 1707번)

2021.11.22 - [알고리즘] - DFS : 아침 산책(백준 21606번)

2021.11.22 - [알고리즘] - DFS : 연산자 끼워넣기(백준 14888번)