[Python] 🥇 백준 7576- 토마토 / BFS 알고리즘 이용하기

 

 

예제 입력 1

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

예제 출력 1

8

 

 

예제 입력 2

6 4
0 -1 0 0 0 0
-1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

예제 출력 2

-1

 

 

 

아이디어 생각하기

이 문제는 익은 토마토들의 주위를 확인하며 나아가야하므로 bfs 알고리즘을 사용해야한다

또한 미로 문제와 다르게 시작점이 여러개이므로, 1인 토마토의 위치값을 모두 큐에 넣어준다

 

 

로직 순서

 

(1) 토마토 박스에 토마토 넣어주기

(2) 익은 토마토들의 위치를 q에 넣어주기

🌟🌟🌟출발점이 여러개인 경우 출발점을 모~두 Queue에 미리 넣어야 한다.🌟🌟🌟

(3) bfs 함수 실행

  -1 큐에서 익은 토마토들의 위치를 popleft

  -2 for문을 4번 돌며 익은 토마토들의 상하좌우를 확인하며 이동할 위치를 만든다

  -3 while문을 돌며 q가 빌 때까지 토마토를 익힌다.

      - if문을 통해 이동할 위치가 박스 안에 있고, 토마토가 안 익었다면 (0), 다음 위치에 기존 토마토값 +1를 넣어준다(토마         토를 익힌다) 

       -q에 이동한 토마토의 위치를 넣어준다. (6) 다시 while 문을 통해 q에서 토마토의 위치를 꺼내고 과정을 반복한다.  

(4) while문이 끝났다는 건 토마토를 익힐만큼 익혔다는 것.  for문으로  박스 안에 토마토들을 확인한다. 만약 0인 값이 있다면 익히지 못하는 토마토이므로 -1를 출력한 후 종료한다.

(5)  토마토가 다 익었다면(0인 값이 없다면), 박스에서 가장 큰 토마토 값에서 -1을 하고 출력한다

처음 시작할 때, 익은 토마토들의 값이 1이므로, 1을 빼준다. 만약 익은 토마토 값이 0, 안 익은 토마토가 1이라면 안 빼도 된다.

 

자세한 것은 아래 주석코드를 보며 확인하면 될 것 같다!

 

 

정답 코드

 

 

주석 있는 코드

"""
토마토 골드 5
"""
import sys
from collections import deque
input = sys.stdin.readline

m,n = map(int, input().split())
box = []
for i in range(n):
    box.append(list(map(int, input().split())))

#상하좌우 방향
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

""" 큐에 1인 토마토값을 초기화
🌟🌟🌟출발점이 여러개인 경우 출발점을 모~두 Queue에 미리 넣어야 한다.🌟🌟🌟
시작점 익은 토마토(1)인 토마토 위치 큐에 append
 1 -1 0 0 0 0
 0 -1 0 0 0 0
 0 0 0 0 -1 0     큐에 1인 토마토들의 위치가 입력된다
 0 0 0 0 -1 1      deque([(0, 0), (3, 5)])
"""
q = deque([])
for i in range(n):
    for j in range(m):
        if box[i][j] == 1: #1인 값들이 q에 들어감
            q.append([i, j])

def bfs():
     while q:
         x, y = q.popleft() #익은 토마토들의 위치를 꺼냄
         for i in range(4):  # 현재 위치에서 상하좌우 확인
             nextX = x + dx[i]  # 새로 이동할 위치
             nextY = y + dy[i]
             # 범위 확인: 범위 안에 있고, 토마토 상태가 0인 경우
             if 0 <= nextX < n and 0 <= nextY < m and box[nextX][nextY] == 0:
                box[nextX][nextY] = box[x][y] + 1 #기존 토마토값 +1 박스에 넣음
                q.append([nextX, nextY]) #q에 토마토 위치를 넣어줌
bfs()
answer = 0
# for문으로 박스 안에 토마토들을 확인한다. 
#box = [[1, -1, 7, 6, 5, 4], 
#       [2, -1, 6, 5, 4, 3],  
#       [3, 4, 5, 6, -1, 2], 
#       [4, 5, 6, 7, -1, 1]]  
# 만약 0인 값이 있다면 익히지 못하는 토마토이므로 -1를 출력한 후 종료한다.
for line in box:
     for tomato in line:
         if tomato == 0:# 안익은 토마토(0)이 있으면 -1 출력 후바로 종료
             print(-1)
             exit(0)
     answer = max(answer, max(line)) #박스 안에서 다 익었으면 최댓값이 정답
print(answer-1) #처음 익은 토마토 1에서 시작했기 때문에 -1

 

주석없는 코드

"""
토마토 골드 5
"""
import sys
from collections import deque
input = sys.stdin.readline

m,n = map(int, input().split())
box = []
for i in range(n):
    box.append(list(map(int, input().split())))

#상하좌우 방향
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

q = deque([])
for i in range(n):
    for j in range(m):
        if box[i][j] == 1:
            q.append([i, j])

def bfs():
     while q:
         x, y = q.popleft()
         for i in range(4):  
             nextX = x + dx[i] 
             nextY = y + dy[i]
             if 0 <= nextX < n and 0 <= nextY < m and box[nextX][nextY] == 0:
                box[nextX][nextY] = box[x][y] + 1 
                q.append([nextX, nextY])
bfs()

answer = 0
for line in box:
     for tomato in line:
         if tomato == 0:
             print(-1)
             exit(0)
     answer = max(answer, max(line)) 
print(answer-1)