[baekjoon] 백준 7576번 : 토마토 (by python) with 너비 우선 탐색 bfs

https://www.acmicpc.net/problem/7576

7576번: 토마토

 

정답 code

#토마토
import sys
from collections import deque
input = sys.stdin.readline

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

def bfs():
    while queue:
        x, y = queue.popleft()
        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 box[nx][ny] == 0:
                box[nx][ny] = box[x][y] + 1
                queue.append([nx,ny])

#입력 받기
m ,n = map(int,input().split())
box = [list(map(int,input().split())) for _ in range(n)]

queue = deque([])
res = 0 #결과값 저장

for i in range(n): #익은 토마토 찾아서 큐에 추가
    for j in range(m):
        if box[i][j] == 1:
            queue.append([i, j])

bfs()
for i in box:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)
    res = max(res,max(i))

print(res-1) #원래 토마토가 1이니 1을 빼준 값이 날짜

 

solution

이번 문제는 한눈에 bfs를 활용해서 풀어야 함을 알 수있었다.

하지만 시작지점이 하나일 수 도있고 여러 개일 수도 있다는것이 주의 할 포인트이다.(익은토마토가 여러개인 경우)

-이 과정을 처리해야하기 때문에 평범한 bfs 문제처럼 보이지만 골드문제 인것 같다.

이 과정에서 생각을 좀 했지만 queue를 함수 밖에서 선언하고 익은토마토를 찾아 먼저 선언 하는게 포인트이다

 

해결 방법은 이중 for문을 통해 익은 토마토를 찾아 배열에 추가한뒤 bfs함수를 실행 하면된다.

 

bfs함수에서는 dx dy에 저장해논 좌표를 이용해 현재 위치해서 상하좌우 탐색을 하게된다.

(최근 풀었던 유사문제로 2178번)

만약 익지 않은 토마토가 있다면 이동해온 토마토에 저장되있던 수 +1을 하고

큐에 추가해준다

 

이런식으로 탐색을 끝내면 box리스트 속 최대값 -1 한값이 모두 익을때까지 소요된 날짜다.

(첫 토마토가 1로 시작을 하기때문)

 

하지만 문제에서 토마토가 모두익지 못하는 상황에서는 -1을 출력해야 함으로 box안에 익지 않은 토마토 (숫자 0) 

이 있다면 -1을 출력하고 없다면 res에 최대값을 저장하고 출력하면 된다