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

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

이번 "백준 - 토마토"문제는 "백준7576번 문제"와 거의 같은 문제입니다. 7576번 문제와 다른 점은 하나의 위 아래로 박스가 추가되었다는 점입니다.

 

위 아래로 박스가 추가되었기 때문에 방향도 마찬가지로 앞, 뒤가 추가되었습니다.

 

접근 방법도 마찬가지로 동일합니다.

 

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

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

---

 

왼쪽 그림과 같이 앞 뒤에 있는 위치까지 생각하여 계산해야 합니다.

 

이는 3차원 배열에서 한 토마토의 위치에서 상, 하, 좌, 우와 더불어 앞, 뒤 총 6방향으로 토마토가 익어나갈 수 있음을 의미합니다.

 

이러한 3차원적 전파를 BFS를 통해 구현하여 모든 토마토가 익는데 걸리는 최소 시간을 계산할 수 있습니다.

 

예를 들어 현재 토마토가 (1,1,1) 위치에 있다면:

• 상: (0,1,1)
• 하: (2,1,1)
• 좌: (1,0,1)
• 우: (1,2,1)
• 앞: (1,1,0)
• 뒤: (1,1,2)

이렇게 6방향으로 토마토가 익어나갈 수 있습니다.

 

 

 

 

 

---

전체 코드

 

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

 

1. static 변수

• N, M, H
  • 상자의 세로(행), 가로(열), 높이를 저장

[JAVA] 좌표와 2차원 배열 매핑의 이해 (좌표 ➡️ 배열)

N과 M을 좌표형식으로 받아야하기 때문에 기존의 행열처럼 [행][열], [가로][세로]가 아닌 M은 가로, N은 세로로 입력받습니다. 이는 좌표평면에서 (x,y) 형식을 따르기 위함입니다.

---

 

• box
  • 토마토의 상태를 저장하는 3차원 배열
• queue
  • BFS에서 익은 토마토의 위치를 저장하는 큐
• days
  • 토마토가 모두 익는데 걸리는 최소 날짜
• dx, dy, dz
  • 6방향(상,하,좌,우,앞,뒤)을 나타내는 방향 배열

이러한 static 변수들은 전역적으로 사용되어 메서드 간에 데이터를 공유하는 데 사용됩니다.

 

2. main 문

 

main 문제에서는 BufferedReader클래스를 사용하여 입력을 빠르게 받아주고, StringTokenizer 클래스를 사용하여 공백을 기준으로 토큰으로 분리해주었습니다.

 

그리고 static 변수를 초기화해주고, 토마토의 상태를 저장하는 배열인 box에다가 값을 넣어줍니다.

 

마지막으로 bfs함수를 호출합니다.

 

3. bfs 함수

 

bfs함수에서는 각 레벨별로 그래프 탐색을 시작합니다. size 만큼 반복문을 돌림으로써 같은 날짜에 익은 토마토들을 한꺼번에 처리할 수 있습니다.

size는 현재 레벨에서 처리해야 할 토마토의 개수를 나타내기 때문입니다.

예를 들어 첫 번째 레벨에서 size가 3이라면, 이는 처음부터 익어있던 토마토가 3개라는 의미이고, 이 3개의 토마토가 동시에 주변 토마토들에게 영향을 미치게 됩니다.

이처럼 size를 통해 같은 시점에 영향을 미치는 토마토들을 함께 처리함으로써, 정확한 일수 계산이 가능해집니다. 만약 size로 구분하지 않는다면, 서로 다른 날짜에 익어야 할 토마토들이 섞여서 처리될 수 있기 때문입니다.

 

큐에서 현재 위치를 꺼내고(poll), 해당 위치에서 6방향(상,하,좌,우,앞,뒤)으로의 탐색을 진행합니다. 

1. 범위 체크: 새로운 위치(nx,ny,nz)가 상자 범위 내에 있는지 확인
2. 익지 않은 토마토 체크: box[nz][nx][ny] == 0 인지 확인
3. 토마토 익히기: 조건을 만족하면 해당 위치의 토마토를 익힘(1로 변경)
4. 위치 저장: 새롭게 익은 토마토의 위치를 큐에 추가

레벨의 모든 토마토를 처리한 후, 큐가 비어있지 않다면(다음 날에 익을 토마토가 있다면) days를 증가시킵니다. 

큐에는 새롭게 익은 토마토의 위치가 저장되어 있습니다. 즉, 다음날에 영향을 미칠 수 있는 토마토들의 위치가 저장되어 있는 것입니다.

만약 큐가 비어있다면, 이는 더 이상 익을 수 있는 토마토가 없다는 것을 의미합니다. 이는 모든 토마토가 익었거나(정상 종료), 더 이상 익힐 수 없는 토마토가 남아있는 경우(비정상 종료)가 될 수 있습니다.

 

이 과정을 큐가 빌 때까지(더 이상 익을 토마토가 없을 때까지) 반복합니다.

 

4. checkTomato 함수

 

checkTomate 함수에서는 간단하게 전체 박스의 토마토를 순회하면서 0이 있는 지 없는 지 체크를 합니다.

 

0이 있다는 의미는 BFS함수를 통해 탐색을 했음에도 익지 않은 토마토가 남아있다는 의미입니다. 이는 토마토가 모두 익지 못하는 상황이므로 -1을 반환합니다.

 

반대로 0이 없다면 모든 토마토가 익었다는 의미이므로 days를 반환하여 토마토가 모두 익는데 걸린 최소 일수를 출력합니다.