[백준] 2573번 빙산(python)

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

2573번: 빙산

 

1. 난이도 골드4 (🥇)

 

2. 문제 해결 과정

 

주의해야 할 점

 

1. 전체 빙산의 녹는 양을 한 번에 빼줘야 한다.

=> 하나 빼주고, 다시 다른 거 빼주고,, 이런식으로 각각 반복하면 바다가 되어버렸을 경우 문제가 발생한다. 

 

2. 처음부터 빙산이 없을 수도 있다. 

 

코드 분석

 

1. 행과 열, 빙산의 정보를 입력받는다.

from collections import deque

n,m = map(int, input().split()) #n행 m열

iceberg = [list(map(int, input().split())) for _ in range(n)] #빙산의 정보

 

2. BFS를 돌며 상하좌우를 확인한다. 빙산과 접해 있을 경우엔 queue에 새로운 빙산 좌표를 넣어주고,

바다와 접해있을 경우엔 인접한 면의 개수만큼 visit[빙산좌표]에 카운트해준다.

=> 각 빙산에 인접해있는 바다의 칸 수가 visit에 담긴다.

def bfs(i,j):
  q = []
  q = deque()
  q.append((i,j))
  visit[i][j] = 0

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

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

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

      if nx<0 or ny<0 or nx>=n or ny>=m:
        continue
      
      if iceberg[nx][ny] == 0: #바다를 만나면 빙산의 좌표(x,y)에 바다 칸 수를 추가해줌
        visit[x][y] += 1
        continue

      if iceberg[nx][ny] != 0 and visit[nx][ny] == -1: #방문하지 않은 빙산을 만나면 queue에 넣어줌
        visit[nx][ny] = 0
        q.append((nx,ny))

 

3. map에 있는 빙산의 덩어리만큼 bfs를 실행시킨다.

=> 빙산의 개수가 cnt에 담긴다.

year = 0 #시간의 흐름 체크

while True:
  cnt = 0 #빙산 덩어리 개수 
  visit = [[-1] * m for _ in range(n)]
  
  for i in range(n): #현재 있는 빙산의 개수 확인
    for j in range(m):
      if visit[i][j] == -1 and iceberg[i][j] != 0:
        bfs(i,j)
        cnt+=1

 

4. 빙산이 2개 이상인지 혹은 다 녹아버렸는지 확인한다.

  if cnt == 0: #빙산이 다 녹을 때까지 두 덩어리로 분리되지 않음
    print(0)
    break
  elif cnt >= 2: #빙산이 두 덩어리로 분리됨
    print(year)
    break

 

5. 빙산이 아직 남아있다면 visit를 이용해 빙산을 녹여준다. 이 때, 바다였거나 바다가 되었으면 0을 넣어준다.

  for i in range(n): 
    for j in range(m):
      # 바다거나 빙산이 녹아서 바다가 된 경우 0
      if iceberg[i][j] == 0 or iceberg[i][j] - visit[i][j] < 0:
        iceberg[i][j] = 0
      # 아직 빙산이 남아있다면 바다가 둘러쌓인 만큼 녹음
      else:
        iceberg[i][j] -= visit[i][j] 

  year += 1

 

4. 전체 코드

from collections import deque

n,m = map(int, input().split()) #n행 m열

iceberg = [list(map(int, input().split())) for _ in range(n)] #빙산의 정보

def bfs(i,j):
  q = []
  q = deque()
  q.append((i,j))
  visit[i][j] = 0

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

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

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

      if nx<0 or ny<0 or nx>=n or ny>=m:
        continue
      
      if iceberg[nx][ny] == 0: #바다를 만나면 육지의 좌표(x,y)에 빙하의 개수를 추가해줌
        visit[x][y] += 1
        continue

      if iceberg[nx][ny] != 0 and visit[nx][ny] == -1: #방문하지 않은 육지를 만나면 queue에 넣어줌
        visit[nx][ny] = 0
        q.append((nx,ny))

year = 0 #시간의 흐름 체크

while True:
  cnt = 0 #빙산 덩어리 개수 
  visit = [[-1] * m for _ in range(n)]
  
  for i in range(n): #현재 있는 빙산의 개수 확인
    for j in range(m):
      if visit[i][j] == -1 and iceberg[i][j] != 0:
        bfs(i,j)
        cnt+=1

  if cnt == 0: #빙산이 다 녹을 때까지 두 덩어리로 분리되지 않음
    print(0)
    break
  elif cnt >= 2: #빙산이 두 덩어리로 분리됨
    print(year)
    break

  for i in range(n): 
    for j in range(m):
      # 바다거나 빙산이 녹아서 바다가 된 경우 0
      if iceberg[i][j] == 0 or iceberg[i][j] - visit[i][j] < 0:
        iceberg[i][j] = 0
      # 아직 빙산이 남아있다면 바다가 둘러쌓인 만큼 녹음
      else:
        iceberg[i][j] -= visit[i][j] 

  year += 1