백준(BOJ) 2573 빙산(Python)

 

그래프 탐색 문제.

빙산 한 번 줄이고 BFS로 빙산 덩어리 개수 찾고

또 빙산 한 번 줄이고 BFS로 빙산 덩어리 개수 찾고

이 과정을 빙산 덩어리가 2개 혹은 빙산이 더 없을 때까지 반복하면 된다.

이때 주의할 점은, 빙산을 줄일 때 순차적으로 줄여나가면 이미 줄인 빙산이 다음에 줄일 빙산에 영향을 주기 때문에

빙산이 줄어드는 높이를 다른 테이블에 따로 관리해줘야 한다는 것이다.

​

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
import math
from itertools import product
from itertools import combinations
"""
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
#input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)

n,m=map(int,input().split())

L=[list(map(int,input().split())) for _ in range(n)]

M=[[0]*m for _ in range(n)]

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

count_zero=0
for i in range(n):
    for j in range(m):
        if L[i][j]==0:
            count_zero+=1

def func():
    global n,m
    visited=[[0]*m for _ in range(n)]
    count=0
    for i in range(n):
        for j in range(m):
            if L[i][j]-M[i][j]>0 and not visited[i][j]:
                queue=deque()
                queue.append([i,j])
                visited[i][j]=1
                count+=1
                while queue:
                    x,y=queue.popleft()
                    for k in range(4):
                        nx=x+dx[k]
                        ny=y+dy[k]
                        if 0<=nx<n and 0<=ny<m and L[nx][ny]-M[nx][ny]>0 and not visited[nx][ny]:
                            queue.append([nx,ny])
                            visited[nx][ny]=1
    return count

result=func()

if result>=2:
    print(0)
else:
    ans=1
    flag=0
    while count_zero<n*m:
        for x in range(n):
            for y in range(m):
                if L[x][y]:
                    for k in range(4):
                        nx=x+dx[k]
                        ny=y+dy[k]
                        if 0<=nx<n and 0<=ny<m and L[nx][ny]==0:
                            M[x][y]+=1
        result=func()
        if result>=2:
            print(ans)
            flag=1
            break
        ans+=1
        count_zero=0
        for x in range(n):
            for y in range(m):
                if L[x][y]-M[x][y]<=0:
                    count_zero+=1
                    L[x][y]=0
                    M[x][y]=0
                else:
                    L[x][y]-=M[x][y]
                    M[x][y]=0
    if not flag:
        print(0)

 

재활을 해야한다.