[백준] 7576번: 토마토

🔍 문제 읽기

7576번: 토마토

 

입력	출력
가로 크기 M, 세로 크기 N N*M 크기의 상자에 담긴 토마토 정보 (1: 익은 토마토, 0: 익지 않은 토마토, -1: 토마토 없음)	토마토가 모두 익을 때까지의 최소 날짜 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력 토마토가 모두 익지는 못하는 상황이면 -1을 출력

 

 

💡풀이 

👩‍💻 사용언어 : cpp

❗️[핵심] 다차원 배열에서의 BFS (너비 우선)

👉 BFS는 너비 우선이기에 최단시간을 구할 수 있다.

 

 

❗️문제 풀이 아이디어

1️⃣ 토마토가 모두 익을 때까지의 최소 날짜?

익은 토마토를 큐에 넣고 BFS를 실행한다.

이때, 토마토가 없는 칸과 이미 방문한 칸에 대하여 주의한다.

 

큐가 빌 때까지 모든 BFS의 수행을 마친 다음,

시간 정보를 저장한 N*M 배열에서 최대 값을 찾는다.

그 값이 토마토가 모드 익을 때까지의 최소 날짜다.

 

 

2️⃣ 토마토가 모두 익지 못하는 상황?

N*M 배열을 이중 반복문을 통해 검사한다.

만약, ①토마토가 있지만 ②방문한 적이 없다면 토마토가 모두 익지 못한 상황이다.

①과 ②를 모두 만족하면 -1을 출력하고 프로그램을 종료시킨다.

 

 

 

🧩 코드