백준 boj 파이썬 2573 빙산

빙산을 녹일 때 주의해야할 점은

원래 빙산이었다가 녹아서 0이 된 점이 주변 빙산을 녹게하면 안된다는 점이다.

이것은 ch 혹은 visit배열로 해결 가능

그리고 처음에 두 덩이로 분리된다는 것이 무슨 뜻인지 해석이 안되어 힘들었다.

이것은 bfs로 지역 탐색했을 때 2 지역 이상 나오면 된다라고 해석하면 된다.

쉬워보이지만 구현할 때 잔실수도 많이 할 수 있어 주의해야한다.

 

얼음을 녹이고->시간 증가->bfs지역 탐색 순으로 반복하면 된다.

 

import sys
from collections import deque
from itertools import combinations
from typing import List, Literal
 
 
 
def bfs(x,y):
    
    q.append((x,y))
    
    while q:
        x,y=q.popleft()
        ok=0
        for k in range(4):
            nx=x+dx[k]
            ny=y+dy[k]
 
            if 0<=nx<n and 0<=ny<m:
                if board[nx][ny]==0 and ch[nx][ny]==-1: ##빙산이 0일 때 ch를 추가한 이유 원래 빙산이었따가 녹은것도 -1 되는 것을 방지하기 위함
                    board[x][y]=max(0,board[x][y]-1)
                    ok+=1
                else: ##빙산이 0이 아닐때
                    if ch[nx][ny]==-1:
                        q.append((nx,ny))
                        ch[nx][ny]=1
 
     
 
def check():
    cnt=0
    visit=[[-1]*m for _ in range(n)]
    for i in range(n):
        for j in range(m): 
            if board[i][j]>0 and visit[i][j]==-1:
                visit[i][j]=1
                q.append((i,j))
                cnt+=1
                while q:
                    
                    x,y=q.popleft()
 
                    for k in range(4):
                        nx=x+dx[k]
                        ny=y+dy[k]
                        if 0<=nx<n and 0<=ny<m:
                            if board[nx][ny]>0 and visit[nx][ny]==-1:
                                q.append((nx,ny))
                                visit[nx][ny]=1
 
    return cnt
 
 
                
 
if __name__=='__main__':
    #sys.stdin=open("input2.txt", "rt")
 
    n,m=map(int,input().split()) ##n=행 m=열
    
    board=[list(map(int,input().split())) for _ in range(n)]
 
    
    time=0
    dx=[0,0,-1,1]
    dy=[1,-1,0,0]
    q=deque()
    #sc=0 ##두덩이 분리전0 두덩이 분리후 1
    
    while True:
        #print(time)
        #for i in range(n):
        #     for j in range(m):
        #                print('%-2d'%board[i][j],end=' ')
        #     print()
        #print()
        ch=[[-1]*m for _ in range(n)]
       
        for i in range(n):
            for j in range(m):
                
                if board[i][j]>0:
                   
                    if ch[i][j]==-1:
                        ch[i][j]=1
                        bfs(i,j)
                  
        time+=1
       
        if check()>=2:
            print(time)
            exit()
        elif check()==0:
            print(0)
            exit()