[bfs/백준] 2573번 : 빙산

- 문제 : https://www.acmicpc.net/problem/2573

 

풀이는 맞았는데, 62%에서 시간초과났다 

풀이로직은 

1. 각 빙하마다 접하는 바닷가 개수 각각 저장하기

2. 1년 후 바닷가 갯수만큼 빙하 크기가 줄어들게하기(각각 줄어들게 하면, 빙하의 바다 접하는 면 수가 달라질 수 있으므로 ice에 담아 놓고 한번에 빼기)

3. 빙하 덩어리 계산하기(이거는 전에 풀었던 bfs문제들과 로직이 똑같다. 방문하지 않고, 0이 아닌 값 부분에 bfs를 하고, 이것의 갯수를 세면된다)

 

빙하 접하는 바다 갯수 구하는 거랑 빙하 영역 구하는게 로직이 좀 겹쳐서 시간초과가 났던 것 같다. 

이 부분은 정답 풀이 보면서 수정했다 

 

- 정답 풀이 :

from collections import deque
import sys
input=sys.stdin.readline

n,m=map(int,input().split())
data=[]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
for _ in range(n):
    data.append(list(map(int,input().split())))
    
def bfs(x,y):
    queue=deque()
    queue.append((x,y))
    visit[x][y]=1
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<n and 0<=ny<m:
                if not visit[nx][ny] and data[nx][ny]!=0:
                    queue.append((nx,ny))
                    visit[nx][ny]=1
                elif data[nx][ny]==0:
                    ice[x][y]+=1                  
                    
year=0  
flag=False
while True: 
    count=0   
    year+=1
    ice=[[0]*m for _ in range(n)]
    visit=[[0]*m for _ in range(n)]  
    for i in range(n):
        for j in range(m):
            if not visit[i][j] and data[i][j] != 0:
                count+=1
                bfs(i,j)             
    for i in range(n):
        for j in range(m):
            data[i][j]-=ice[i][j]
            if data[i][j]<0:
                data[i][j]=0                
    if count==0:
        break
    if count>1:
        flag=True
        break
if flag:
    print(year-1)
else:
    print(0)

 

from collections import deque
import sys
input=sys.stdin.readline

n,m=map(int,input().split())
data=[]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
for _ in range(n):
    data.append(list(map(int,input().split())))
    
#각 빙하별로 바닷가 닿는 부분 계산하기 
def melt(x,y):
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0 <= nx < n and 0 <= ny < m :
            if data[nx][ny]==0:
                ice[x][y]+=1

def bfs(x,y):
    queue=deque()
    queue.append((x,y))
    visit[x][y]=1
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<n and 0<=ny<m:
                if not visit[nx][ny] and data[nx][ny]!=0:
                    queue.append((nx,ny))
                    visit[nx][ny]=1
                    
year=0   
flag=False
while True: 
    count=0   
    year+=1
    ice=[[0]*m for _ in range(n)]
    visit=[[0]*m for _ in range(n)]      
    #bfs를 먼저하고
    for i in range(n):
        for j in range(m):
            if not visit[i][j] and data[i][j] != 0:
                bfs(i,j)
                count+=1
                
    for i in range(n):
        for j in range(m):
            if data[i][j]!=0:
                melt(i,j)
                
    for i in range(n):
        for j in range(m):
            data[i][j]-=ice[i][j]
            if data[i][j]<0:
                data[i][j]=0
                
    #종료 조건 하나더 추가하면 이 풀이도 정답!    
    if count==0:
        break        
    if count>1:
        flag=True
        break
if flag:
    print(year-1)
else:
    print(0)

 

- 시도해본 풀이 :

from collections import deque
import sys
input=sys.stdin.readline

n,m=map(int,input().split())
data=[]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
for _ in range(n):
    data.append(list(map(int,input().split())))
    
#각 빙하별로 바닷가 닿는 부분 계산하기 
def melt(x,y):
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0 <= nx < n and 0 <= ny < m :
            if data[nx][ny]==0:
                ice[x][y]+=1

def bfs(x,y):
    queue=deque()
    queue.append((x,y))
    visit[x][y]=1
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<n and 0<=ny<m:
                if not visit[nx][ny] and data[nx][ny]!=0:
                    queue.append((nx,ny))
                    visit[nx][ny]=1
                    
year=0                    
while True: 
    count=0   
    year+=1
    ice=[[0]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if data[i][j]!=0:
                melt(i,j)
                
    for i in range(n):
        for j in range(m):
            data[i][j]-=ice[i][j]
            if data[i][j]<0:
                data[i][j]=0
                
    visit=[[0]*m for _ in range(n)]              
    for i in range(n):
        for j in range(m):
            if not visit[i][j] and data[i][j] != 0:
                bfs(i,j)
                count+=1
    if count>1:
        break
print(year)