[백준] 7576 토마토 파이썬 풀이 (BFS)

코드

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


def bfs(M, N, box):
    # 좌우상하
    dx = [0, 0, 1, -1]
    dy = [-1, 1, 0, 0]

    days = -1

    while ripe: #ripe가 비지 않았을 동안
        days += 1
        for _ in range(len(ripe)):
            x, y = ripe.popleft() 
            # print(f'x는 {x} y는 {y}')
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                if (0 <= nx < N) and (0 <= ny < M) and (box[nx][ny] == 0):
                    box[nx][ny] = 1 #익은 상태로 바꾼다
                    ripe.append([nx, ny])

    for b in box:
        if 0 in b:
            return -1
    return days


M, N = map(int, r().split())
box, ripe = [], deque()
for i in range(N):
    row = list(map(int, r().split()))
    for j in range(M):
        if row[j] == 1:
            ripe.append([i, j]) #익은 토마토 ripe에 넣음
    box.append(row) #box 리스트 채움


print(bfs(M, N, box))

 

 

 

풀이

 

이 문제는 토마토가 하루마다 주변에 있는 모든 토마토들이 한번에 변하므로

한 방향으로 탐색하는 dfs가 아닌 주변부에 있는 것부터 탐색하는 bfs로 풀어야한다.

 

 

먼저 입력받은 값을 box에 다 채워주고

ripe에 1이 있는 (익은) 토마토들을 넣어준다.

 

그리고 bfs를 실행한다

 

 

dx는 x좌표를 움직이는 것

dy는 y좌표를 움직이는 것이다

둘이 합치면

[0]은 x좌표를 그대로, y좌표를 -1 → box[x][y-1]  → 좌

[1]은 x좌표 그대로 , y좌표 +1 → box[x][y+1] → 우

[2]는 x좌표 +1, y좌표 그대로 → box[x+1][y] → 하

[3]는 x좌표-1 , y좌표 그대로 → box[x-1][y] → 상

 

ripe에 아무것도 없을때까지 while문을 돌린다.

입력 1을 보면 지금은 box[3][5] 만 1이므로 ripe에 [3,5]가 담겨있다.

ripe에서 맨 앞에 원소를 꺼내서 x,y에 담으면 x=3, y=5가 된다.

 

좌우상하를 돌면서 box의 범위를 벗어나지 않고 해당 값이 0이면 (익지 않았으면)

1로 바꾸고 ripe에 해당 위치를 넣는다.

다시 while문을 돈다.

..

반복

 

 

while문이 끝나고 나서

box안에 0이 하나라도 있으면 -1을 출력한다.

 

 

---

day는 상하좌우는 하루만에 익으므로 for문안에 넣으면 안되고

while문 시작할 때 넣어야한다.

그리고 첫날에는 원래 익은 토마토로 인해 익는 토마토가 익기때문에

day를 처음에는 -1로 지정해준다.

(첫날은 day=0인데 이때 원래 익은 토마토 + 새로익은 토마토가 생기기 때문)