백준 2573 | 빙산 | Python 풀이

문제

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

2573번: 빙산

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

 

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

 

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

 

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

 

내 답안

# 2573 빙산
import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
time = 0  # 시간의 경과
direction = [(-1, 0), (1, 0), (0, 1), (0, -1)]  # 이동 방향

# 주변 탐색
def bfs(x, y):
  q = deque([(x, y)])
  visited[x][y] = 1

  while q:
    cx, cy = q.popleft()  # 현 위치
    for dx, dy in direction:
      nx, ny = cx + dx, cy + dy
      if (0 <= nx < n and 0 <= ny < m):
        if graph[nx][ny] == 0:  # 현 위치 주변이 바다
          visited[cx][cy] += 1  # 바다 개수 저장

        if visited[nx][ny] == 0 and graph[nx][ny] != 0:  # 현 위치 주변이 빙산
          q.append((nx, ny))
          visited[nx][ny] = 1

while True:
  count = 0  # 이번년도에 생성된 빙산 덩어리 수
  visited = [[0] * m for _ in range(n)]  # 방문 여부
  
  # 빙산 덩어리 탐색
  for i in range(n):
    for j in range(m):
      if visited[i][j] == 0 and graph[i][j] > 0:
        bfs(i, j)
        count += 1  # bfs로 찾은 빙산 덩어리 카운트

  # 빙산 녹이기
  for i in range(n):
    for j in range(m):
      if visited[i][j] != 0:
        graph[i][j] -= (visited[i][j] - 1)
        if graph[i][j] < 0:
          graph[i][j] = 0

  # 빙산 덩어리 검사
  if count >= 2:
    print(time)
    break

  if count == 0:
    print(0)
    break

  time += 1  # 1년 흐름

해설

빙산 덩어리가 2개 이상이 되기 전까지 매 년 while 문을 반복한다.

 

while 내부에서는 BFS로 주변 바다의 개수를 저장하고와  인접한 빙산 덩어리를 방문한다. 이후 주변 바다의 수 만큼 해당 빙산을 녹이고, 빙산이 두 덩어리 이상으로 분리되었는지 검사하여 while 문을 계속할 것인지 결정한다.

 

이 과정을 구체적으로 설명하자면 다음과 같다. (while 문 내부 설명)

 

1. 당해의 빙산 덩어리 수를 저장할 count 변수, 빙산의 방문 여부를 기록하고 주변 바다의 개수를 저장할 visited 리스트를 준비한다. 
2. for 문을 순회하며 빙산 덩어리와 주변 바다의 개수를 센다.
   1. 당해 방문하지 않은 빙산이라면 현 위치에서 탐색을 시작해야 하므로 bfs 함수를 호출한다.
   2. 현 위치에서 출발하여 한 덩어리를 이룰 빙산들을 저장할 큐를 준비한다. 
   3. 큐에 빙산이 없을 때까지 즉, 한 덩어리를 이루는 빙산을 모두 방문하기 전까지 인접한 위치를 탐색한다.
      1. 인접한 지점이 바다라면, 현 위치의 visited 값에 +1 한다.
      2. 인접한 지점이 빙산이라면, 방문을 기록하고 큐에다 넣는다. 
3. for 문을 순회하며 앞 단계(2번)에서 계산된 주변 바다 수만큼 빙산을 녹인다. 이 때, 값이 음수가 될 수 없으므로 0 미만의 값이 되면 0으로 맞춰준다.
4.  앞앞 단계(2번)에서 계산된 빙산 덩어리 수를 조사하여 두 덩이 이상이거나, 빙산덩어리가 하나도 없다면 답을 출력하고 while 문을 종료한다. 
5. time 변수에 +1 해 줌으로써 시간의 흐름(1년)을 기록한다. 

피드백 및 주의사항

• 처음에는 bfs 탐색 기준을 '바다'로 두고 현 위치가 바다일 때마다 주변의 빙산을 녹이는(1씩 감소시키는) 방식으로 접근했었다. 이 삽질을 한시간 가까이 하다가 이게 아닌걸 느껴서 다른 사람의 풀이를 참고했다.
• bfs 탐색 기준을 '빙산'으로 두고, 한 덩어리를 이루는 빙산들을 방문하면서 각 빙산마다 인근 바다의 개수를 저장해야 한다. 이때 한 빙산에서 바다를 만나는 즉시 녹이면 안되고, 한 덩어리 탐색이 완전히 끝난 후 한꺼번에 빙산을 녹여야 한다.
• visited 리스트 하나로 방문을 기록하면서 주변 바다의 개수를 저장하도록 하니 메모리 공간이 조금 더 효율적으로 운용되었다.