백준 2573. 빙산 (With. Python)

백준 2573. 빙산

BFS 알고리즘 써야하는 거 몰랐으면 손도 못 댔을 것 같다 ㅎㅁㅎ..

쉬운데 어렵다 ㅋㅋㅋㅋ 어떻게 푸는 지 조금만 간단하게 생각하면 쉽게 풀었을 것 같은데 조건이 많다보니 이것저것 재면서 굉장쓰 복잡쓰 꼬여버렸음 ㅠㅠ

🎈 풀이

1. 빙산이 다 녹아서 없거나 (0 출력), 두 덩이로 쪼개지면 (시간 출력) 알고리즘이 끝난다.
2. 빙산은 처음 상태에서 상하좌우로 둘러쌓인 물(0)의 개수만큼 높이가 깎인다. (높이는 0 이상)

그럼 체크해야할 사항을 생각해보면 크게 3가지가 있다.

• 물과 인접한 빙산의 얼음을 녹인다. (높이를 줄인다.) 단, 같은 단계에서 빙산이 녹아 만들어진 물은 다른 빙산이 녹는 것에 영향을 주지 않는다. 이를 방지하기 위해 counted를 활용한다.
• 빙산이 한 번 녹은 후, 빙산의 더미 개수를 체크한다.
• 더미 개수가 0개이면 즉, 다 녹았으면 0을, 1개이면 시간 +1을, 2개 이상이면 시간을 출력한다.

여기서 counted 방식을 생각하지 못했다 ㅠㅠ 그리고 이중 반복문에서 bfs를 돌리면서 더미 개수도 바로바로 확인할 수 있었던 것..!!

우선 counted는 bfs를 돌리면서 해당 위치의 빙산의 상하좌우에 물이 있으면 counted의 같은 위치에 +1씩 해주어 저장한다. 그리고 빙산 리스트를 모두 돈 후에, counted를 돌면서 해당 위치의 빙산의 높이를 깍아준다.

또한, 빙산 리스트를 돌면서 bfs 알고리즘을 진행할 때마다 특정 변수에 +1씩 해준다. 그럼 모두 돌고 나서 특정 변수가 1이면 더미가 1개, 0이면 다 녹았음, 2개 이상이면 더미가 2개 이상임을 의미한다.

그래서 모두 취합하여 구현하면
👇👇👇👇

🎈 코드

from collections import deque

# bfs
# 상하좌우로 인접한 빙하 방문
# 인접한 물(0)이 있으면 counted 리스트 업데이트
def bfs(i, j):
  queue = deque()
  queue.append([i,j])

  while queue:
    x, y = queue.popleft()
    for (h, w) in [[1,0],[0,1],[-1,0],[0,-1]]:
      dx, dy = x+h, y+w
      if 0<=dx<n and 0<=dy<m: 
        if graph[dx][dy]!=0 and not visited[dx][dy]:
          visited[dx][dy] = 1
          queue.append([dx,dy])
        elif graph[dx][dy]==0:
          # 빙하[x][y]와 인접한 물(0)의 개수
          counted[x][y] += 1
      

# 입력값
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

# 알고리즘이 끝나는 시간
res = 0

while 1:
  visited = [[0]*m for _ in range(n)] # 방문 리스트
  counted = [[0]*m for _ in range(n)] # 인접한 물의 개수 리스트

  dummy = 0 # 빙하 더미 개수

  for i in range(n):
    for j in range(m):
      if graph[i][j]!=0 and not visited[i][j]:
        visited[i][j] = 1
        bfs(i, j) # bfs
        dummy += 1 # 더미 +1

  # 빙하 깎기
  for i in range(n):
    for j in range(m):
      if graph[i][j]>=counted[i][j]:
        graph[i][j] -= counted[i][j]
      else:
        graph[i][j] = 0

  # 빙하 더미가 2개 이상 (알고리즘 종료 조건)
  if dummy>=2:
    print(res)
    break
  # 빙하 더미가 없음 : 다 녹았을 때 (알고리즘 종료 조건)
  elif not dummy:
    print(0)
    break
  # 빙하 더미가 1개
  else:
    res += 1