[BOJ 7569] 토마토(JAVA, BFS, QUEUE)

https://www.acmicpc.net/problem/7569

7569번: 토마토

 

 

1. 익은 토마토 위치 구하고 큐에 넣기

 

 

 

2. 큐에 들은 아이템을 기반으로 BFS 탐색을 통해서, 더 이상 익은 토마토가 추가되지 않으면 종료.

 * 큐에 들은 아이템을 이용, 토마토 배열을 탐색하면 시간초과 발생.

 

 

 

해설코드(C++).

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
    static int[][][] arr;
    static int[][] op = {{1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1}};
    static int N, M, H;
    static Scanner sc;
    static int answer = 0, total = 0, cur = 0;
    static Queue<item> q;
    
    public static void main (String[] args) throws java.lang.Exception
    {
        sc = new Scanner(System.in);
        q = new LinkedList<>();
        
        M = sc.nextInt();
        N = sc.nextInt();
        H = sc.nextInt();
        arr = new int[H + 1][N + 1][M + 1];
        
        for(int i = 1; i <= H; i++){
            for(int j = 1 ; j <= N; j++){
                for(int k = 1; k <= M; k++){
                    arr[i][j][k] = sc.nextInt();
                    if(arr[i][j][k] == 0)
                        total += 1;
                    else if(arr[i][j][k] == 1)
                        q.add(new item(i, j, k, 0));
                }
            }
        }
        
        while(!q.isEmpty()){
            item qItem = q.poll();
            
            int h = qItem.h;
            int r = qItem.r;
            int c = qItem.c;
            int d = qItem.day;
            answer = d;
            
            for(int i = 0; i < 6; i++){
                int n_h = h + op[i][0];
                int n_r = r + op[i][1];
                int n_c = c + op[i][2];
                
                if(n_h < 1 || n_h > H || n_r < 1 || n_r > N || n_c < 1 || n_c > M)
                    continue;
                    
                if(arr[n_h][n_r][n_c] == 0){
                    arr[n_h][n_r][n_c] = 1;
                    cur += 1;
                    q.add(new item(n_h, n_r, n_c, d + 1));
                }
            }
        }
        
        if(cur == total)
            System.out.println(answer);
        else
            System.out.println(-1);
    }
}
 
class item{
    int r, c, h, day;
    
    public item(int h, int r, int c, int d) {
        this.h = h;
        this.r = r;
        this.c = c;
        this.day = d;
    }
}