[백준_7576] 토마토 by python ( BFS )

문제

접근법

[문제에 대한 이해]

 

처음에 문제를 풀 때, 첫번째 예시가 어떻게 8일만에 모두 숙성됬는지에 대해서 이해가 잘 안됬다.

 

사실 아래 그림처럼, day2에서 접근할 수 있는 자리의 수를 2로 변경한거는 결과를 얻었을 때 얻어낸 방법론이고

실제로 처음 접근했을 때는 모두 1로 표기를 하였습니다.

 

결과적으로는, 이 문제는 최초 익은 토마토(=1)를 기점으로 주변 ( 상,하,좌,우 ) 이 익어가는데 걸리는 총 시간을 구하면 되기 때문에 BFS를 통해 결과값을 얻을 수 있다. 

 

[문제에 대한 접근]

 

1. 어떻게 하면 3*3 시리즈와 같이 떨어져있는 익은 토마토의 주변을 동시에 숙성 시킬 수 있을까?

 

여태까지 구현을 해왔던 DFS or BFS 코드에서는 사실 조건이 충족된다면 바로 Function을 호출 했기 때문에 ! 모든 값들을 queue에 저장하고 가는 모습이 쉽게 떠오르지 않았다.

 

하지만, 검색 + 생각을 하다보니 최초에 주어진 1의 양이 생각보다 많지 않다는 것을 배울 수 있었고 이를 통해 모든 1의 좌표를 deque에 담아주었다.

 

2. 어떻게 하면, 최종 일수를 구할 수 있을까?

 

아까 이야기 했던 것처럼, 최초에 문제에 접근 했을 때 토마토가 익어가는 과정을 모두 1로 표기 했었다.

그러다보니 정리하는 과정 속에서도 내가 queue 순서에 맞게 제대로 하고 있는 것일까 라는 의문을 가졌는데 ! 이 때 접근법이 나름 떠올랐다.

 

결과적으로는 모두 익는데 소요되는 시간을 걸리는 것이기 때문에 이전 토마토가 익는데 걸린 시간에서 +1 한 값들을 꾸준히 전달을 해준다면 최종적으로 가장 큰 값이 우리의 농장 토마토가 모두 익는 시간이라는 것을 알 수 있었다.

 

이를 통해, 하나 더 얻을 수 있는 정보는 만약 BFS가 완료가 되었는데도 불구하고 '0'이 남아있다면 익을 수 있는 상태에 있는 토마토가 존재한다는 것이기 때문에 이를 응용하여 문제를 풀었다.

코드

import sys
from collections import deque
input = sys.stdin.readline # input보다 엄청나게 빠름 => 입출력이 많을 때 사용하자.

dx = [1, -1, 0 ,0] 
dy = [0, 0, 1, -1]
# m이 가로 n이 세로
m, n = map(int, input().split())
farm = []

for i in range(n):
    farm.append(list(map(int, input().split())))

queue = deque() # deque는 stack + queue 역할이 모두 가능 

for i in range(n):
    for j in range(m):
        if farm[i][j] == 1:
            queue.append([i,j]) # 최초 농장의 모든 1을 deque에 담는다.

def bfs():
    global queue
    while queue:
        a, b = queue.popleft()
        for i in range(4): # 상,하,좌,우 체크
            x = a + dx[i]
            y = b + dy[i]
            if 0 <= x < n and 0 <= y < m and farm[x][y] == 0:
                farm[x][y] = farm[a][b]+1 # 이 전 토마토의 일수 + 1
                queue.append([x,y])

def check():
    answer = 0
    for i in range(n):
        for j in range(m):
            tmp = farm[i][j]
            if tmp == 0: # 다 돌았을 때, 0이 있다는 것은 숙성이 불가능한 토마토가 있다는 것과 같다.
                print(-1)
                return
            answer = max(answer, tmp) # 가장 큰 값 == 최종일 
    print(answer-1) # 최초 시작일이 1이기에 -1 해줘야 한다.
bfs()
check()