[boj] 백준 2573 빙산 python 풀이

현 상태에서 녹을 수 있는 빙하를 받아서 한 번에 녹이기

-> 섬 갯수 찾기(bfs)

를 반복하여 풀이

 

문제

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

4963번: 섬의 개수

 

코드

import sys
input = sys.stdin.readline
import collections

N, M = map(int,input().split())
MAP = []


for i in range(N):
    tmp = list(map(int,input().split()))
    MAP.append(tmp)

move = {(-1,0), (0,1), (1,0), (0,-1)}

def melting(MAP):
    will_melt = set()
    for i in range(N):
        for j in range(M):
            cnt = 0
            if MAP[i][j] > 0:
                for tx, ty in move: 
                    nx = tx + i
                    ny = ty + j

                    if 0<=nx<N and 0<=ny<M and MAP[nx][ny] == 0:
                        cnt += 1
            if cnt > 0:
                will_melt.add((i,j,cnt))
    
    for x,y,cnt in will_melt:
        MAP[x][y] = max(0, MAP[x][y] - cnt)

    return will_melt

def bfs(x,y,MAP,visited):
    q = collections.deque()
    q.append((x,y))
    visited[x][y] = 1

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

        for tx, ty in move:
            nx = tx + x
            ny = ty + y

            if 0<=nx<N and 0<=ny<M and MAP[nx][ny] > 0 and visited[nx][ny] == 0:
                visited[nx][ny] = 1
                q.append((nx,ny))

def check_dummy(MAP):
    visited = [[ 0 for _ in range(M)]for _ in range(N)]
    dummy = 0
    for i in range(N):
        for j in range(M):
            if visited[i][j] == 0 and MAP[i][j] > 0:
                if dummy >0:
                    return dummy+1
                bfs(i,j, MAP, visited)
                dummy += 1

    return dummy

time = 0
while True:
    n_mountain = melting(MAP)    
    time += 1

    if check_dummy(MAP)>1:
        print(time)
        break

    if not n_mountain:
        print(0)
        break