파이썬) 2573 빙산

메모:

import sys
from collections import deque
input=sys.stdin.readline
n,m=map(int,input().split())
#빙산 리스트 생성
ice_list=[]
num=0
for i in range(n):
    m_list=list(map(int,input().split()))
    ice_list.append(m_list)
    num=num+sum(m_list)


#bfs 
def bfs(start_x, start_y, graph,num):
    
    #상 하 좌 우
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    #비교할 합
    temp_sum=0
    #내년의 합
    next_sum=0
    
    queue = deque([(start_x, start_y)])
    visited = set([(start_x, start_y)])


    # print(graph)
    while queue:
        x, y = queue.popleft()
        temp_sum+=graph[x][y]

        zero_count=0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if graph[nx][ny]==0:
                zero_count+=1
            elif graph[nx][ny]!=0:
                if (nx, ny) not in visited:
                    visited.add((nx, ny))
                    queue.append((nx, ny))
        #내년 리스트 값 넣어주기
        next=ice_list[x][y]-zero_count
        if next>0:
            next_year[x][y]=next
            next_sum+=next
    # print(temp_sum,num)
    if temp_sum!=num:
        return -1
    return next_sum


#년 수 
year=0
#bfs로 년 수 카운팅
while(True):
    #내년 리스트
    next_year=[[0 for i in range(m)] for j in range(n)]
    #빙산에서 0이 아닌 수를 찾음.
    x=-1 
    y=-1
    for i in range(n):
        for j in range(m):
            if ice_list[i][j]!=0:
                x,y=i,j
                
    #리스트가 다 0이면
    if x==-1 and y==-1:
        print(0)
        break
    #0이 아닌 수의 x,y로 bfs 시작.
    count=bfs(x,y,ice_list,num)
    
    #정답 출력
    if count==-1:
        print(year)
        break
    else:
        num=count
    ice_list=next_year.copy()
    year+=1

 

 

처음생각했던거

bfs에 양수 하나를 넣어서 

가다가 상하좌우가 다 0인 수가 나오면 얼음이 2개이므로 break

-->bfs에 들어간 수가 상하좌우가 0이 나올수가 없다. ㅋㅋ

 

수정한거

빙산의 숫자 총 합을 기록해서

bfs를 돌렸을때 숫자들을 합친거랑 다르면

얼음이 2개이므로 break

-->굿

 

 

 

문제가 생겼던 곳

  # print(graph)
    while queue:
        x, y = queue.popleft()
        temp_sum+=graph[x][y]

        zero_count=0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if graph[nx][ny]==0:
                zero_count+=1
            elif graph[nx][ny]!=0:
                if (nx, ny) not in visited:
                    visited.add((nx, ny))
                    queue.append((nx, ny))
        #내년 리스트 값 넣어주기
        next=ice_list[x][y]-zero_count
        if next>0:
            next_year[x][y]=next
            next_sum+=next
    # print(temp_sum,num)
    if temp_sum!=num:
        return 0
    return next_sum

여기서 next_sum이 0이 될때랑(모두 한번에 다 녹을 때)

if temp_sum!=num: return 0 이랑 겹쳐서 다른 값이 나왔었다.