[python] 백준 2573 :: 빙산 (DFS)

[빙산]

# 문제
지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 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을 출력한다.

풀이

0. 풀이 방법

• 얼음인 곳을 기준으로 DFS 탐색을 한다.
• 탐색을 하면서 현재 얼음과 맞닿아 있는 바다의 개수를 파악한다.
• 탐색을 하면서 얼음인 곳을 만나면 얼음의 위치를 stack에 저장해두고,
  stack의 요소들을 기준으로 탐색을 이어간다.
• DFS 탐색이 한 턴 완료되면 연결된 얼음 한 덩어리를 모두 돌게 된다.
  (연결된 얼음들은 stack에 넣어놓아서 이어서 탐색하니까!)
• DFS 탐색을 하는 횟수가 얼음 덩어리라는 것을 활용해 빙산의 덩어리 수를 구한다.

 

1. 입력 받기

• 입력 받은 이차원 배열을 매번 모두 체크하지 않도록 얼음 좌표만 모아서 ice dict에 저장한다.
• 얼음이 있는 곳만 넣을 거니까 얼음이 있다는 표시로 값에 1을 넣어둔다.
  (이 좌표의 얼음이 녹으면 0으로 바꿀 거임!)

# 입력 받기
row_len, col_len = map(int, input().split())
arr = []
for _ in range(row_len):
    arr.append(list(map(int, sys.stdin.readline().split())))

ice = {}  # 얼음 좌표만 모은 dict - 키: tuple(행, 열), 값: 1(얼음 있음) or 0(얼음 없음)
for i in range(1, row_len-1):  # 첫 번째 행과 열, 마지막 행과 열에는 얼음이 없으니 1부터 마지막 전까지 반복
    for j in range(1, col_len-1):
        if arr[i][j]:
            ice[(i, j)] = 1  # 얼음이 있는 부분 ice에 추가

 

2. 빙산을 기준으로 DFS 탐색 ㄱㄱ

• 탐색하면서 빙산을 만나게 되면 다음에 탐색할 수 있도록 linked_ice stack에 넣어둘 것이다.
• 일단 처음 들어온 좌표를 linked_ice stack에 넣고 탐색 시작-!

def DFS(row_i, col_i):
    linked_ice = [(row_i, col_i)]  # 현재 얼음에 연결된 얼음 좌표들을 추가할 stack

 

• stack에서 한 요소를 가져와서 해당 요소를 기준으로 탐색을 한다.

    while linked_ice:  # 연결된 얼음이 있는 동안 반복
        item = linked_ice.pop()

 

• 이미 방문한 얼음인지 확인하고, 방문하지 않은 얼음일 때만 진행
• 방문 체크 ㄱㄱ
• 현재 좌표에 연결된 바다 개수를 담을 변수 water_count를 초기화한다.

        if not visited_ice[item[0]][item[1]]:
            visited_ice[item[0]][item[1]] = True

            water_count = 0  # 상하좌우 중에 바다인 곳 개수

 

상하좌우 체크

• 함수 외부에 dy, dx를 만들어 두고, 상하좌우를 체크할 때 활용한다.

  dy = [-1, 0, 1, 0]
  dx = [0, 1, 0, -1]

 

• row와 col에 dy, dx를 하나씩 더해줘서 for문 안에서 상하좌우 좌표를 만들어준다.

            for i in range(4):
                row = item[0] + dy[i]
                col = item[1] + dx[i]

 

• 이제 좌표는 상하좌우 중 하나의 위치를 갖게 된다.
• 🚨 여기서도 방문 여부를 체크해줘야 한다.
  그 이유는,
  얼음이었다가 이번 턴에 물로 바뀐 영역은 물로 세면 안되기 때문!!!
  1년이 지날 때 한번에 싹 녹아버리는 거니까, 같은 해에 녹아서 물이 된 영역은 아직 얼음이라고 생각해줘야 한다.
• 이걸 체크하기 위해서 방문 체크 배열 visited_ice를 활용한다.
  얼음일 경우만 방문 체크가 True로 바뀌어 있을 것이므로, 방문 체크가 True라면 얼음이라고 생각하면 됨. (물인지 아닌지 탐색할 필요가 없다.)

                # 얼음이었다가 물이 된 부분을 재탐색 하는 것 방지 (얼음이었다가 이번 해에 물이 된 부분은 True로 바뀌어있음)
                if not visited_ice[row][col]:

 

바다인지 빙산인지 확인

• 값이 0보다 같거나 작으면 바다이므로 water_count에 1을 추가해준다.
  (바다인 부분은 처음에 0이 들어가지만, 이후 계산에서 마이너스 값을 가질 수 있기 때문에 0보다 같거나 작은 경우로 조건을 작성해야 한다.)
• 값이 0보다 크다면 얼음이므로 linked_ice stack에 추가해준다.

                    if arr[row][col] <= 0:  # 바다이면
                        water_count += 1
                    else:  # 빙산이면
                        linked_ice.append((row, col))

 

바다 수만큼 빙산 녹이기

• 계산한 water_count 값만큼 빙산의 좌표에서 차감한다.
• 빙산의 좌표에서 water_count를 차감했을 때 값이 0보다 같거나 작으면 빙산이 모두 녹은 것이니까, 빙산을 체크하는 dict ice의 값을 0으로 바꾼다.

            arr[item[0]][item[1]] -= water_count

            if arr[item[0]][item[1]] <= 0:  # 높이가 0보다 같거나 작아지면 빙산 녹음 처리
                ice[(item[0], item[1])] = 0

 

3. 탐색을 진행하면서 빙산 덩어리의 수를 파악한다.

• 종료 조건: 빙산 덩어리가 두 개가 되거나 빙산이 모두 녹을 때까지 반복한다.
• 빙산이 전부 녹는 것이 빙산이 두 덩어리가 되는 것보다 더 늦으니, 이 조건으로 while문을 작성한다.

year = 0
while sum(ice.values()) > 0:  # 얼음이 전부 녹을때까지 반복

 

빙산 덩어리 수 파악

• DFS 함수가 한번 호출되면, 연결된 얼음을 stack에 담아가면서 탐색을 이어가기 때문에 연결된 빙산은 모두 돌고 함수가 종료된다.
• 따라서, 한 해에 DFS가 호출된 횟수가 빙산 덩어리의 수이다.
• dfs_count에 DFS가 호출된 횟수를 담아서 덩어리의 수를 파악한다.

    dfs_count = 1  # DSF 탐색 횟수 == 빙산 덩어리 수

 

• 방문 여부를 체크할 배열을 이 while문 안에서 만들어준다.
• 방문을 했던 빙산이더라도, 해가 바뀌면 또 방문해야 하니까! 새롭게 만들어줘야 하기 때문!!

    visited_ice = [[False]*col_len for _ in range(row_len)]

 

• 빙산의 좌표만 모아놓은 ice에서 빙산의 좌표를 하나씩 가져온다.
• 이전 해에 녹아서 바다가 되지는 않았는지,(if value)
  이미 방문한 좌표는 아닌지 확인한다. (not visited_ice[key[0]][key[1]])

    for key, value in ice.items():
        if value and not visited_ice[key[0]][key[1]]:

 

• 빙산 덩어리의 수를 의미하는 dfs_count가 2가 되면 반복문을 탈출한다. (break)
• 여기서 탈출되지 않았으면 빙산 덩어리가 2가 되지 않은 것이니, for문 바로 다음에 해(year)를 늘리고 다시 탐색 하게 한다.(continue)
• 빙산 덩어리가 2가 되었으면 break를 만나 for문을 탈출했겠지만, while문은 여전히 돌고 있다. 따라서 while문도 탈출하기 위해서 while문 바로 다음에 break문을 한번 더 작성해준다.

            if dfs_count == 2:  # 빙산 덩어리가 2가 되면 for문 종료
                print(year)
                break
            DFS(key[0], key[1])
            dfs_count += 1
    else:  # 빙산 덩어리가 2가 되지 않았으면 while문 반복
        year += 1
        continue
    break  # 빙산 덩어리가 2가 되었으면 while문 종료

 

• while문을 탈출하지 못하고 모든 좌표의 값이 0이 될 때까지 돌고 종료된 경우에는 덩어리가 2가 되는 시점이 없다는 의미이므로 else문에서 0을 출력한다.

else:
    print(0)

 

 

끝!

 

전체 코드

import sys

# 입력 받기
row_len, col_len = map(int, input().split())
arr = []
for _ in range(row_len):
    arr.append(list(map(int, sys.stdin.readline().split())))

ice = {}  # 얼음 좌표만 모은 dict - 키: tuple(행, 열), 값: 1(얼음 있음) or 0(얼음 없음)
for i in range(1, row_len-1):  # 첫 번째 행과 열, 마지막 행과 열에는 얼음이 없으니 1부터 마지막 전까지 반복
    for j in range(1, col_len-1):
        if arr[i][j]:
            ice[(i, j)] = 1  # 얼음이 있는 부분 ice에 추가

dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]


def DFS(row_i, col_i):
    linked_ice = [(row_i, col_i)]  # 현재 얼음에 연결된 얼음 좌표들을 추가할 stack

    while linked_ice:  # 연결된 얼음이 있는 동안 반복
        item = linked_ice.pop()
        if not visited_ice[item[0]][item[1]]:
            visited_ice[item[0]][item[1]] = True

            water_count = 0  # 상하좌우 중에 바다인 곳 개수

            for i in range(4):
                row = item[0] + dy[i]
                col = item[1] + dx[i]

                # 얼음이었다가 물이 된 부분을 재탐색 하는 것 방지 (얼음이었다가 이번 해에 물이 된 부분은 True로 바뀌어있음)
                if not visited_ice[row][col]:
                    if arr[row][col] <= 0:  # 바다이면
                        water_count += 1
                    else:  # 빙산이면
                        linked_ice.append((row, col))

            arr[item[0]][item[1]] -= water_count

            if arr[item[0]][item[1]] <= 0:  # 높이가 0보다 같거나 작아지면 빙산 녹음 처리
                ice[(item[0], item[1])] = 0


year = 0
while sum(ice.values()) > 0:  # 얼음이 전부 녹을때까지 반복
    dfs_count = 1  # DSF 탐색 횟수 == 빙산 덩어리 수
    visited_ice = [[False]*col_len for _ in range(row_len)]

    for key, value in ice.items():
        if value and not visited_ice[key[0]][key[1]]:
            if dfs_count == 2:  # 빙산 덩어리가 2가 되면 for문 종료
                print(year)
                break
            DFS(key[0], key[1])
            dfs_count += 1
    else:  # 빙산 덩어리가 2가 되지 않았으면 while문 반복
        year += 1
        continue
    break  # 빙산 덩어리가 2가 되었으면 while문 종료

else:
    print(0)