[백준]2573번 빙산 (Python/파이썬)

1. 문제

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

 

 

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

그림 1의 1년 후 모습. 한 덩어리.

 

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

 

그림 1의 2년 후, 그림 2의 1년 후 모습. 세 덩어리.

 

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

 

문제 해석

이 문제는 2468번 안전 영역과 2667번 단지번호붙이기 문제와 비슷하게 풀 수 있습니다.

 

 

최단 경로/시간을 구하는 문제이므로 너비우선탐색(BFS)을 사용할 겁니다.

BFS 함수는 아래와 같이 동작해야 합니다:

하나의 칸(노드)에서 위/아래/좌/우 총 네 가지 방향을 고려한 다음,

   1) 바다(0)가 인접한 경우 노드 값에 -1을 하여 높이를 깎고,

   2) 높이가 0보다 큰 노드와 인접한 경우 탐색 대상 큐에 넣어줍니다.

 

전체 코드는 다음과 같이 동작해야 합니다:

높이 > 0인 모든 노드에 대해서, year가 +1씩 증가할 때마다 아래와 같은 동작을 수행합니다.

   1) 인접 노드 = 0, 현재 노드의 높이 -1

   2) 인접 노드 > 0, search_Q.append(인접노드)

   3) 높이 = 0인 노드를 빙산 리스트에서 제거

 

저는 초기 답안에 3)을 빼먹고 작성하다가 틀렸습니다.

모든 빙산이 사라질 때까지 빙산 덩어리(높이 > 0인 노드가 상/하/좌/우로 모여 있는 영역)를 찾아야 하는데, 반복문의 조건을 알 수가 없습니다.

반복문의 수행 범위를 가장 높은 높이값으로 정한다면, 바다에 둘러싸여 있지 않은 빙산에 대해서는 미처 다 녹이지 못하고 종료되어 hidden case에서 오류가 발생합니다(3%에서 틀렸습니다가 나왔습니다🤦‍♀️).

조건을 알 수 없으니, BFS 구현 방식과 동일하게 탐색 대상인 빙산의 리스트가 없어지기 전까지 돌아가도록 while문을 사용해야 합니다.

이때, 다 녹아서 사라진 빙산들은 탐색 대상 리스트에서 제거해줘야겠죠.

그래서 3) 부분을 main에서 구현하는 것이 중요합니다.

---

2. 입/출력

1) 입력

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다.

 

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

 

2) 출력

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

 

📌 main에서의 while문은 빙산 덩어리 개수 > 1이 되는 순간 year를 출력하고 종료합니다.

📌 while문에서 코드가 종료되지 않으면, 0을 출력합니다.

 

3) 예제

# Input
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

# Output : 2

 

---

3. 구현 코드

1) Main 함수

N, M = map(int, input().split())

mountains = []
need_search = []
for i in range(N):
    mountains.append(list(map(int, input().split())))
    for j in range(M):
        if mountains[i][j] > 0:
            need_search.append((i, j))

 

입력 값 N, M을 받고, 빙산의 높이와 바다(0)를 2차원 배열 mountains에 저장합니다.

이때, 노드의 값(높이)이 0보다 큰 경우, 탐색 대상이므로 need_search 리스트에 넣어줍니다.

year = 0
while need_search:
    visited = [[0 for _ in range(M)] for _ in range(N)]
    del_data = []
    cnt = 0

    for i, j in need_search:
        if mountains[i][j] > 0 and visited[i][j] == 0:
            bfs(i, j, visited)
            cnt += 1

        if mountains[i][j] == 0:
            del_data.append((i, j))

    if cnt > 1:
        print(year)
        exit()

    year += 1
    need_search = sorted(list(set(need_search) - set(del_data)))

print(0)

 

빙하가 두 덩어리 이상으로 쪼개지는 최초 시간(년도)을 구하기 위해 while문 밖에 year=0을 정의합니다.

녹지 않은 빙하 리스트(need_search)가 존재하는 동안, 반복문이 동작합니다.

 

각 연도마다 빙하에 대한 방문 여부를 표기하는 visited 배열과, 녹은 빙하를 체크하기 위한 del_data 배열을 선언합니다.

방문한 적 없고, 녹지 않은 빙하(need_search)의 각 빙하를 시작 노드로 하여 BFS를 수행한 후, 영역을 1개 더해줍니다.

이때, 녹은 빙하가 있다면 del_data에 넣습니다.

 

need_search 내에서의 BFS 탐색이 종료된 후, 영역의 개수가 1보다 크다면(2개 이상 쪼개짐) year를 출력하고 종료합니다.

그렇지 않다면, year에 +1을 하고 need_search에서 del_data를 지워줍니다.

 

모든 빙하가 녹아 need_search는 빈 리스트가 되고, 반복문이 종료된다면 빙하 영역이 쪼개지지 않은 경우이므로 0을 출력합니다.

 

2) BFS 함수

from collections import deque

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

def bfs(i, j, visited):
    queue = deque([(i, j)])
    visited[i][j] = 1

    while queue:
        x, y = queue.popleft()

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if nx < 0 or nx >= N or ny < 0 or ny >= M: continue
            if visited[nx][ny]: continue

            if mountains[nx][ny] == 0 and mountains[x][y] > 0:
                mountains[x][y] -= 1

            elif mountains[nx][ny] > 0:
                visited[nx][ny] = 1
                queue.append((nx, ny))

 

현재 노드(x, y)의 상하좌우 노드(nx, ny)에 대해

• 방문한 적이 없는 경우(visited[nx][ny] = False)
  • 현재 노드 높이를 깎아야 하는지(mountains[nx][ny]=0)
  • 탐색큐에 추가해야 되는지(mountains[nx][ny] > 0)

확인하고 동작을 수행합니다.

 

3) 전체 코드

from collections import deque

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

def bfs(i, j, visited):
    queue = deque([(i, j)])
    visited[i][j] = 1

    while queue:
        x, y = queue.popleft()

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if nx < 0 or nx >= N or ny < 0 or ny >= M: continue
            if visited[nx][ny]: continue

            if mountains[nx][ny] == 0 and mountains[x][y] > 0:
                mountains[x][y] -= 1

            elif mountains[nx][ny] > 0:
                visited[nx][ny] = 1
                queue.append((nx, ny))


### Main ###
N, M = map(int, input().split())
mountains = []

need_search = []
for i in range(N):
    mountains.append(list(map(int, input().split())))
    for j in range(M):
        if mountains[i][j] > 0:
            need_search.append((i, j))


year = 0
while need_search:
    visited = [[0 for _ in range(M)] for _ in range(N)]
    del_data = []
    cnt = 0

    for i, j in need_search:
        if mountains[i][j] > 0 and visited[i][j] == 0:
            bfs(i, j, visited)
            cnt += 1

        if mountains[i][j] == 0:
            del_data.append((i, j))

    if cnt > 1:
        print(year)
        exit()

    year += 1
    need_search = sorted(list(set(need_search) - set(del_data)))

print(0)

 

---

4. 출처/유사한 문제

1) 문제 출처

https://www.acmicpc.net/problem/2573

2573번: 빙산

 

백준의 골드4 문제이고, 아래 블로그의 코드를 참고해 제 답안을 보완했습니다.

https://yuuki0930.tistory.com/55

[백준 파이썬] 2573 빙산

 

2) 유사한 문제

비가 오는 높이에 따라 잠기는 영역과 잠기지 않는 영역이 생기는 안전 영역 구하기 문제(실버1)와 유사합니다.

2차원 배열에 높이 값을 저장하고, 비의 높이가 변함에 따라 잠기지 않는 영역(덩어리)의 최댓값을 구해서 출력하는 문제입니다.

 

2024.04.19 - [코딩테스트] - [백준]2468번 안전 영역 (Python/파이썬) - 시간 초과 해결

[백준]2468번 안전 영역 (Python/파이썬) - 시간 초과 해결