[python] 7576 토마토 - 백준 / 출발지점이 여러개인 bfs 가 헷갈릴 때 다시볼것

import sys 
from collections import deque

def bfs(M,N , queue):

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

    while queue :
        # check_point 기준으로 상하 좌우의 값을 탐색합니다.
        x ,y =queue.popleft()
        num = tomato[x][y]
        num+=1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or nx >= N or ny < 0 or ny >= M :
                continue

            if tomato[nx][ny] == -1 :
                continue

            if tomato[nx][ny] == 0 :
                tomato[nx][ny] = num
                queue.append([nx,ny])

            if tomato[nx][ny] > 1:
                if tomato[nx][ny] >= num:
                    tomato[nx][ny] = num
                    queue.append([nx,ny])


    # 0이 남아있을때 / max 값을 리턴합니다. 

    max = 0
    for i in range(M):
        for j in range(N):
            if tomato[j][i] == 0 :
                return -1
            if tomato[j][i] > max :
                max = tomato[j][i]

    return max-1



M,N = map(int , input().split())
tomato = []
for i in range(N):
    tomato.append(list(map(int, input().split())))

# 큐에 처음 1의 값을 가진 숫자들을 넣어줍니다. 
queue = deque()
for i in range(M):
    for j in range(N):
        if tomato[j][i] == 1 :
            queue.append([j , i])

# M,N 과 QUEUE 를 전송해줍니다. 
print(bfs(M,N , queue))

이렇게 만들면 시간 초과가 나온다. 왜인지 20분정도 헤메이다가 다시 솔루션을 찾았다. 

 

import sys 
from collections import deque

def bfs(M,N , queue):
    dx =[1,-1,0,0]
    dy =[0,0,1,-1]

    while queue :
        x ,y =queue.popleft()
        num = tomato[x][y]
        num+=1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or nx >= N or ny < 0 or ny >= M :
                continue

            if tomato[nx][ny] == -1 :
                continue

            if tomato[nx][ny] > 1:
                if tomato[nx][ny] >= num:
                    tomato[nx][ny] = num

            if tomato[nx][ny] == 0 :
                tomato[nx][ny] = num
                queue.append([nx,ny])



    # 0이 남아있을때 / max 값을 리턴합니다. 

    max = 0
    for i in range(M):
        for j in range(N):
            if tomato[j][i] == 0 :
                return -1
            if tomato[j][i] > max :
                max = tomato[j][i]

    return max-1



M,N = map(int , input().split())
tomato = []
for i in range(N):
    tomato.append(list(map(int, input().split())))

# 큐에 처음 1의 값을 가진 숫자들을 넣어줍니다. 
queue = deque()
for i in range(M):
    for j in range(N):
        if tomato[j][i] == 1 :
            queue.append([j , i])

# M,N 과 QUEUE 를 전송해줍니다. 
print(bfs(M,N , queue))

 

tomato >1 이 부분에서 

다시 append 를 하지 않으면 시간 초과가 나오지 않는다. append 를 다시 하지 않아도 그 값에는 별 영향이 없을까? 고민해본다면 

 

일단 tomato[nx][ny] 가 1 보다 크다는 소리는 이미 다른번쨰수가 방문을 했다는 소리이다. 

방문을 했는데 그 값이 최적의 해가 아니라 돌아온 경우의 수 일때.... 

아니 잠깐 구현해보다 든 생각인데 

if tomato[nx][ny] >1 이 줄이 없어도 값이 동일하게 나온다... 

어디서 부터 꼬인걸까 

bfs 에 대한 근본적인 이해를 다시해보는게 중요하다고 느꼈다. 

 

 

 

import sys 
from collections import deque

def bfs(M,N , queue):
    dx =[1,-1,0,0]
    dy =[0,0,1,-1]

    while queue :
        x ,y =queue.popleft()
        num = tomato[x][y]
        num+=1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or nx >= N or ny < 0 or ny >= M :
                continue

            if tomato[nx][ny] == -1 :
                continue

            ''' if tomato[nx][ny] > 1:
                if tomato[nx][ny] >= num:
                    tomato[nx][ny] = num'''

            if tomato[nx][ny] == 0 :
                tomato[nx][ny] = num
                queue.append([nx,ny])

    print(tomato)

    # 0이 남아있을때 / max 값을 리턴합니다. 

    max = 0
    for i in range(M):
        for j in range(N):
            if tomato[j][i] == 0 :
                return -1
            if tomato[j][i] > max :
                max = tomato[j][i]

    return max-1



M,N = map(int , input().split())
tomato = []
for i in range(N):
    tomato.append(list(map(int, input().split())))

# 큐에 처음 1의 값을 가진 숫자들을 넣어줍니다. 
queue = deque()
for i in range(M):
    for j in range(N):
        if tomato[j][i] == 1 :
            queue.append([j , i])

# M,N 과 QUEUE 를 전송해줍니다. 
print(bfs(M,N , queue))

이렇게 중간을 생략해도 답은 동일하게 나온다.

 

 

 

어디서 헷갈린지 모르겠다.일단 다른 코드들을 보면서 배운점들을 설명해보자 

https://jiwon-coding.tistory.com/97

[백준] 7576번 토마토 / 파이썬(python)

 

 

 

from collections import deque
m,n = map(int,input().split())
graph = []
queue = deque([])
for i in range(n):
    graph.append(list(map(int,input().split())))
    
    for j in range(m): #익은 토마토 큐에 저장
        if graph[i][j]==1:
            queue.append([i,j])
            
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def bfs():
    while queue:
        x,y = queue.popleft()
        
        for i in range(4):
            a = x+dx[i]
            b = y+dy[i]
            if 0<=a<n and 0<=b<m and graph[a][b]==0:
                queue.append([a,b])
                graph[a][b] = graph[x][y]+1
bfs()
answ = 0
for i in graph:
    for j in i:
        if j==0:
            print(-1)
            exit(0)
    answ = max(answ,max(i))
print(answ-1)

위의 블로그에서 따왔다.

 

먼저 인상깊었던 코드는 

for i in range(n):

    graph.append(list(map(int,input().split())))

    

    for j in range(m): #익은 토마토 큐에 저장

        if graph[i][j]==1:

            queue.append([i,j])

      

처음 입력받을 때 부터 나와는 다르게 문제를 깔끔하게 푼다는 걸 느꼈다.

나는 반복문 2개를 사용해서 입력을 받았고

실제로 나도 한번에 하기 위해서 끙끙 앓다가..( 반복문 n^2 를 한개만 이용해서 입력도 받고 출발점도 찾으려고 했으나..) 실패했는데 고수들은 역시나 깔끔하게 받는다. 

 

그리고 또 

 

 

      

        for i in range(4):

            a = x+dx[i]

            b = y+dy[i]

            if 0<=a<n and 0<=b<m and graph[a][b]==0:

                queue.append([a,b])

                graph[a][b] = graph[x][y]+1

 

이 부분에서 나는 continue 문을 사용해서 예외를 걸렀다면 

더 짧게 만들 수 있게 '가능한' 경우만 통과시켰다.

 

사실 이 부분은 취향차이 혹은 코드의 필요성에 따라서 달라질 수 있다고 생각하지만 단순히 숏코딩으로만 봤을때는 훨씬 더 효율적이다. 역시 고수들은 다르다 ㅇㅇ..

 

다시한번 보면서 왜틀렸는지 알아보도록하자.

 

 

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

bfs 에 대한 이해를 늘리기 위해서 구글에  " bfs 최단경로 출발점이 여러개일때" 를 검색해 보았다. 

 

별계로 다시 생각해 보았는데 내가 염려한 부분은 겹치는 부분을 염려했던 것 같다. 그런데 조금만 더 깊게 생각해 본다면 이미 0이 아닌 그래프의 값을 다시 계산해 본다고 한들 이미 도착한 값이 최소일 수 밖에 없다.

예를들어서 

1 -1 0

0 0 0

0 0 1  

이런 식일때 가장 중간쪽에서 값들이 반복해서 bfs 의 값을 설정해주는 것이 신경쓰인다고 해보자 

다음 시뮬레이션을 통해서 이해해보자면..

 

1 -1 0

2 0 2

0 2 1

 

1 -1 3

2 3! 2

3! 2 1 

 

이렇게 어디에서든지간에 값의 차이가 없을 수 밖에 없다 ( 실제로 최단거리를 구해도 마찬가지이고..)

 

내가 뭔가 너무나 어렵게 생각한거같다. 분명히 또 헷갈릴때가 올 텐데 제목위에 써두고 두고두고 다시보자