▶2573 - 빙산
▶문제
지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 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을 출력한다.
▶풀이
bfs()를 이용하면 되는 문제지만 조건이 생각보다 까다로웠다.
일단, 빙산의 개수도 파악해야 하고, 녹는 부분도 판단해야 한다.
빙산의 개수는 bfs()가 실행되는 횟수로 정해주었다.
하나라면 bfs()가 한 번만 돌고 끝나기 때문이다.
녹는 부분은 bfs()에서 빙산일 때 주변에 바다의 수를 구해주었다.
처음에는 arr[nx][ny]가 0이면 바로 빼주었는데, 제출하니 실패가 떴다.
이유를 생각해 보니 처음에 바로 녹아서 0이 되면, 다음 빙산은 바다로 판단하기 때문에 실패한 것 같다.
그래서 melt라는 int형 변수를 추가해 주고 바다를 만나면 1을 추가해 주었다.
그다음 for문이 끝나고 녹는 게 있으면 list에 (x, y, melt)를 추가했다.
while이 끝나고 return 해주기 전에 이 부분들을 다 빼주니까 정답이 나왔다.
조건도 생각보다 까다로웠고, 머리를 조금 더 써야 하는 문제였다.
먼저 녹이면 안 되고, 나중에 녹여야 한다는 것을 너무 늦게 알아서, 실패를 몇 번 했었다.
from collections import deque
def bfs(a, b):
queue = deque([(a, b)])
visit[a][b] = 1
melt_list = []
while queue:
x, y = queue.popleft()
melt = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if arr[nx][ny] == 0:
melt += 1
elif arr[nx][ny] != 0 and visit[nx][ny] == 0:
queue.append((nx, ny))
visit[nx][ny] = 1
if melt > 0:
melt_list.append((x, y, melt))
for x, y, melt in melt_list:
arr[x][y] = max(0, arr[x][y] - melt)
return 1
n, m = map(int, input().split())
year = 0
arr, ice = [], []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(n):
a = list(map(int, input().split()))
arr.append(a)
for j in range(m):
if a[j] != 0:
ice.append((i, j))
while ice:
visit = [[0 for _ in range(m)] for _ in range(n)]
count = 0
melt = []
for i, j in ice:
if arr[i][j] != 0 and visit[i][j] == 0:
count += bfs(i, j)
if arr[i][j] == 0:
melt.append((i, j))
if count > 1:
print(year)
break
ice = sorted(list(set(ice) - set(melt)))
year += 1
if count < 2:
print(0)
'BOJ Code > Gold' 카테고리의 다른 글
[백준/BOJ] gold5 - 16234번 인구 이동 (Python) (2) | 2023.03.06 |
---|---|
[백준/BOJ] gold4 - 1963번 소수 경로 (Python) (2) | 2023.03.06 |
[백준/BOJ] gold3 - 2146번 다리 만들기 (Python) (6) | 2023.02.26 |
[백준/BOJ] gold4 - 1715번 카드 정렬하기 (Python) (3) | 2023.02.25 |
[백준/BOJ] gold4 - 3055번 탈출 (Python) (0) | 2023.02.24 |