백준/ Gold 4 문제 , 백준 파이썬 2573, 빙산 [BFS]

백준/ Gold 4 문제 , 백준 파이썬 2573, 빙산 [BFS]

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
바다에서 탐색을하는 식으로 접근했다가 피봤다. 빙산인 부분만 탐색해서 접근하는게 훨씬 낫다

 

문제 출처

 

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

2573번: 빙산

 

 

 

풀이

 

 

1. 기본세팅

 

1. 상하좌우 움직임

 

2. N, M 입력받기

 

3. N행의 빙산 상태 입력받기

 

 

 

2. BFS

나는 처음에 빙산에서 시작하는게 아닌 바다 부터 시작해서 탐색을 하였는데,

 

그러다 보니 생기는 문제가 바로 빙산이 녹는 것을 한번에 처리하기가 어려웠다.

 

그리고 가운데에 빙산이 뚫려있는 형태에서는 bfs가 의도하지않게 추가로 호출 되면서 이 부분에서도 어려움을 느꼈음.

 

 

이후, 빙산을 찾아 탐색을 하고 만나면서 녹이는 것이 아닌 한번에 녹이는 식의 풀이 방법으로 바꿨는데,

 

그러기 위해선 주변에 0이 몇개있는지 카운트해주고 그것을 melting 이라는 리스트에 따로 저장해줬다.

 

 

 

 

 

 

3. BFS 호출 및 리턴값 처리, 빙하 녹이기

 

재탐색을 방지하기 위해 visited 리스트를 선언해주고

 

이중 for 문을 돌면서 빙산을 만나면 BFS 함수를 호출해준다.

 

이때 한번 호출될때마다 cnt 값을 증가시켜주는데, 만약 BFS 함수가 2번이상 호출될 경우,

 

빙산이 분리되어있는 형태이므로 걸린 시간을 출력하고 프로그램을 종료시킨다.

 

cnt가 0 일경우는 빙산이 분리되지 않고 다녹은 상황이므로 0을 출력시킨다.

 

 

while문 마지막에는 위에 BFS 함수에서 세주었던 melting 리스트를 이용하여 빙산을 한번에 녹인다.

 

이런식으로 while문을 돌려가면서 빙산이 분리되는지를 확인한다.

 

 

 

 

정답

 

from collections import deque

vertical=[1,-1,0,0]
parallel=[0,0,1,-1]

N,M=map(int,input().split())
iceberg=[]
for i in range(N):
    iceberg.append(list(map(int,input().split())))

def bfs(x,y,cnt):
    dq=deque()
    dq.append([x,y])
    visited[x][y]=True
    while dq:
        X,Y=dq.popleft()
        for i in range(4):
            mx=X+vertical[i]
            my=Y+parallel[i]
            if 0<=mx<N and 0<=my<M:
                if iceberg[mx][my]!=0 and visited[mx][my]==False:
                    dq.append([mx,my])
                    visited[mx][my]=True
                elif iceberg[mx][my]==0:
                    melting[X][Y]+=1
                    
    return cnt+1

year=0
while True:
    cnt=0
    visited=[[False]*M for _ in range(N)]
    melting=[[0 for _ in range(M)] for _ in range(N)] 
    for i in range(N):
        for j in range(M):
            if iceberg[i][j]!=0 and visited[i][j]==False:
                cnt=bfs(i,j,cnt)
                
    if cnt>=2:
        print(year)
        exit(0)
    if cnt==0:
        print(0)
        exit(0)
    
    for i in range(N):
        for j in range(M):
            iceberg[i][j]-=melting[i][j]
            if iceberg[i][j]<0:
                iceberg[i][j]=0
    year+=1