[Python] 백준 2573번 : 빙산 (G4) - DFS&BFS 필수문제4

#문제

www.acmicpc.net/problem/2573

2573번: 빙산

#풀이 & 학습한 내용

2차원 리스트를 실시간으로 갱신시키면서 그래프탐색을 하면 안되고, 다른 2차원 리스트를 선언후 복사붙여넣기해서 초기의 2차원 리스트를 변형시키지 않고 탐색을 진행해야 하는 문제입니다. 이때 반드시 깊은 복사를 해야되고, 이에 대한 설명은 justdoit709.tistory.com/52에 자세히 나와있습니다.

 

#소스코드

from collections import deque #큐 쓰기위해
import copy #리스트 깊은복사 하기위해
import sys #sys.stdin.readline()위해

dx=[0,0,1,-1]
dy=[1,-1,0,0] #상하좌우 방향

def bfs(q):
  global visited
  temp_q = copy.deepcopy(ices) #깊은복사

  while q:
    v=q.popleft()
    now_x=v[0]
    now_y=v[1] #큐에서 뽑은 vertex의 현재좌표

    for i in range(4):
      new_x=now_x+dx[i]
      new_y=now_y+dy[i]

      if (0<=new_x<N) and (0<=new_y<M): #범위안에 존재할 때
        if ices[new_x][new_y]==0: #바다일때
          temp_q[now_x][now_y]-=1

        #바다가 아닌 빙산이고 방문한 적 없을 때
        elif ices[new_x][new_y] !=0 and not visited[new_x][new_y]:
          visited[new_x][new_y]=True #방문처리
          q.append([new_x,new_y]) #다른 인접한 빙산 탐색위해 큐에 삽입
    
    if temp_q[now_x][now_y]<0: #음수일 경우 0으로 바꿔주기
      temp_q[now_x][now_y]=0
  
  return temp_q #새로 갱신된 빙산분포 return


N,M=map(int,sys.stdin.readline().split())
ices=[list(map(int,sys.stdin.readline().split())) for _ in range(N) ] #빙산분포 2차원 리스트
ans_year=0 #몇년경과해야 두 덩어리 이상이 되는지 저장할 변수

while True:
  block_count=0 # 이번년도 빙산분포는 몇 덩어리인지 저장할 변수

  visited=[[False]*M for _ in range(N)] #이번년도에 빙산들 방문여부

  for i in range(N):
    for j in range(M):
      if ices[i][j]!=0 and not visited[i][j]:
        block_count+=1 #한 덩어리 추가
        q=deque([[i,j]])
        visited[i][j]=True
        ices=bfs(q) #여기서 경로있는 vertex들은 모두 방문처리

  if block_count >=2: #두 덩어리 이상
    print(ans_year)
    break
  
  if block_count==0: #한 덩어리도 없음(=다 녹음)
    print(0)
    break
  
  ans_year+=1 #1년경과
  

github.com/HoYoungChun/Algorithm_PS/blob/master/DFS%26BFS/BOJ_2573.py

HoYoungChun/Algorithm_PS