[BFS] 백준 7569번 토마토 자바 풀이

BOJ 7569번 토마토 문제 자바(java) 풀이

• 난이도: 실버1
• 백준 7569번번 토마토
  
  
  

문제 정리

1. 창고에 보관한 토마토중에 잘 익은 것과 익지 않은 것이 있다.
2. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익게 된다.
3. 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 이다. (대각선 X)
4. 창고의 토마토들이 며칠이 지나면 다 익게 되는지 최소 일수를 구하려 한다.
5. 모든 칸에 토마토가 들어있지 않을 수 있다.
6. 1: 익은 토마토, 0: 익지 않은 토마토, -1: 토마토가 들어있지 않음
7. 저장될 때 부터 모든 토마토가 익어있는 상태이면 0을 출력
8. 토마토가 모두 익지 못한다면 -1 출력
   
   
   

문제 접근

3차원 형태의 배열을 가지고 bfs 탐색을 통해 토마토를 익혀가면 된다.
3차원 형태라고 하지만 기존의 bfs와 같습니다.
다만 보통 상,하,좌,우 네 방향만 탐색하는데 거기에 더 나아가서 6방향 탐색을 하면 됩니다

static int[] xdir = {-1,1,0,0,0,0};
static int[] ydir = {0,0,-1,1,0,0};
static int[] zdir = {0,0,0,0,-1,1};

6방향을 나타내기 위해서 위와 같이 배열을 구성하였습니다
상, 하, 좌, 우, 위, 아래 순서의 방향입니다.

동시에 토마토를 익혀가기 위해서 list에 넣고 모두 꺼내서 큐에 넣어 탐색하면 된다.

문제 풀이

1. 토마토에 대한 정보를 3차원 배열에 모두 저장합니다.
   저장하면서 1인 값은 토마토 위치를 담는 list에 넣습니다.
2. bfs 탐색을 한다. 탐색에 앞서 queue에 토마토의 위치를 모두 담는다. 그렇게 하여 처음의 모든 토마토에서 동시에 익어간다.
3. 6가지 방향으로 탐색합니다. 방향이 유효하고 방문하지 않은 위치의 경우 방문하고 익은 토마토로 표시를 위해 1로 합니다.
4. time 값이 max 보다 큰 경우 max 값을 갱신해나가며 토마토가 모두 익는데 필요한 시간을 저장합니다.
5. 탐색이 모두 끝난 후 max 값이 0이면 이미 모두 익어있던 상태이므로 0을 출력합니다.
6. 그렇지 않은 경우 모두 익었는지 배열을 모두 탐색합니다. 탐색 후 0인 값 즉, 익지 않은 토마토가 있다면 모두 익힐 수 없는 경우 이므로 -1 출력, 0이 없는 경우에는 max 값을 출력한다.
   
   
   

문제 풀이