[백준, 7576번] 토마토 (BFS, 너비 우선 탐색, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - 토마토" 문제는 BFS (너비 우선 탐색) 를 활용하여 풀이하는 전형적인 그래프 탐색 문제입니다.

 

M x N 크기의 상자가 주어지고, 해당 상자의 토마토가 있을 때 다음 조건을 만족하는 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 합니다.

• 보관 후 하루가 지나면 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.
• 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력

---

문제 접근 방법

1. 익은 토마토(1)들을 모두 큐에 넣고 동시에 BFS를 시작합니다.
2. 익지 않은 토마토(0)는 방문하지 않은 노드로 처리하며, 토마토가 없는 칸(-1)은 아예 탐색하지 않습니다.
3. BFS를 수행하면서 토마토가 익어가는 날짜를 갱신합니다.
4. 모든 토마토가 익는 최소 날짜를 구하고, 안 익는 토마토가 있으면 -1을 반환합니다.

---

 

예제 입력 1번을 그림으로 표현하면 위와 같습니다. 예제 1번에서는 전체 토마토가 익을 수 있으며, 전체 토마토가 익는 데 걸리는 시간은 8일입니다.

---

전체 코드

 

이번 문제는 그래프 탐색 알고리즘의 대표적인 문제이기 때문에 BFS 알고리즘이나 DFS알고리즘을 사용할 수 있습니다.

 

BFS는 "모든 토마토가 익는 최소 일수"를 보장해 주는 반면, DFS는 이 문제에선 최단 시간을 보장할 수 없습니다. 따라서 저는 BFS알고리즘을 사용했습니다.

---

저의 코드는 크게 3가지로 구성되어있습니다.

 

1. main 문

 

main문에서는 기본적으로 BufferedReader를 사용하여 빠르게 입력을 받아주었고, 토마토를 상자에 담아주는 로직이 존재합니다.

 

이 때 주의해야할 점은 M -> 가로, N -> 세로여서 [M][N]으로 상자를 초기화 한다면 에러가 발생합니다. 배열의 요소는 [행][열]형식으로 접근합니다. 하지만 좌표는 (x,y)형식으로 표현되며 일반적으로x는 열, y는 행을 나타냅니다.

 

따라서 입력값이 M(가로,열), N(세로,행)으로 주어지더라도 배열을 생성할 때는 [N][M]으로 생성해야 합니다.

 

이렇게 생성된 배열에서 wareHouse[i][j]는 i행 j열의 토마토를 의미하게 됩니다. 또한 초기에 익어있는 토마토(값이 1인 위치)를 발견하면 해당 위치를 queue에 저장하여 BFS 탐색의 시작점으로 사용합니다.

 

2. BFS 알고리즘 함수

 

BFS함수에서는 너비 우선 탐색(BFS) 알고리즘의 특징인 가까운 노드부터 탐색하는 성질을 활용하여 익은 토마토로부터 가장 가까운 토마토부터 순차적으로 익히는 과정을 구현합니다.

1 0 0    // 초기상태: 큐에 (0,0) 위치가 들어있음
0 0 0
0 0 0

1일차: 큐의 size = 1
1 1 0    // (0,0)의 상하좌우 확인 -> 새로운 위치 (0,1), (1,0)이 큐에 추가됨
1 0 0
0 0 0

2일차: 큐의 size = 2
1 1 1    // 큐에 있던 (0,1), (1,0)의 상하좌우 확인
1 1 0    // -> 새로운 위치들이 큐에 추가됨
1 0 0

 

큐(Queue) 자료구조는 BFS에서 핵심적인 역할을 하는데, 같은 날짜에 익은 토마토들을 한번에 처리할 수 있게 해줍니다. 큐의 size만큼 반복문을 돌림으로써 '같은 날짜에 익은 토마토들'을 함께 처리할 수 있습니다.

 

또한 문제에서 토마토는 인접한 방향(상하좌우)에 있는 익은 토마토의 영향을 받아 익게 됩니다. 따라서 큐가 비어있다는 것은 더 이상 주변을 익힐 수 있는 토마토가 없다는 의미이고, 이는 날짜를 증가시킬 필요가 없다는 것을 의미합니다.

 

따라서 큐에 값이 있을 때만 날짜를 증가해줘야 합니다.

 

 

3. checkTomato 함수 : 토마토의 결과를 검증하는 함수

 

해당 함수에서는 모든 토마토가 익었는지 확인합니다.

 

wareHouse 배열을 순회하면서 안 익은 토마토(0)가 하나라도 있다면 false를 반환하고, 모든 토마토가 익었다면 true를 반환합니다.

이 반환값을 통해 bfs 함수에서는:

• true일 경우: 걸린 일수(days)를 출력
• false일 경우: -1을 출력 (토마토가 모두 익지 못하는 상황)

이렇게 문제의 요구사항에 맞는 출력값을 결정하게 됩니다.