문제

---

문제 접근

1. 🤢 기존 그래프 문제에 비해 특이점은 2차원 배열이 아니라 3차원 배열이라는 것을 인지해야 한다는 점이다.

2. 토마토들이 병렬적으로 각각 번지기 때문에 이를 고려하여 루프를 짜야한다

3. 앞뒤상하좌우 라는 방향벡터를 설정해야한다

그외에는 기존 BFS 그래프 탐색과 동일하다고 보인다.

---

1. 전역변수 설정하기

// 1 인 지점부터 시작하여 상하좌우앞뒤로 퍼지게 된다, 관건은 상하에 대한 고려를 해주어야 한다는 점, 방향벡터에 대한 설정이 필요
    // 방향 벡터에 대한 설정, dz 가 추가적으로 들어감, 기본적인 순서는 상하좌우위아래가 됨
    static int[] dx = {-1,1,0,0,0,0};
    static int[] dy = {0,0,-1,1,0,0};
    static int[] dz = {0,0,0,0,-1,1};
    static int tomatoCnt; // 익혀야할 토마토의 개수
    static int[][][] graph;

    static int m,n,h;

    static Queue<Point> queue;

• 0 인 경우 익혀야할 토마토 개수가 증가한다고 하였을 때, BFS를 수행하지 않아도 익혀야할 토마토 개수가 0 인경우에는 바로 반환할 수 있도록 따로 토마토 개수를 저장한다
• 방향 벡터의 경우 고려해야할 점이 상,하 가 있는데 상하좌우위아래의 방향 벡터를 미리 지정한다
• BFS 를 수행하기 전부터 1인 경우에 큐에 담아주어 BFS를 수행할 것이기에 static으로 설정해준다

---

2. 좌표값을 지정할 객체 생성

// 좌표값을 저장할 객체 생성
    static class Point{
        private int z;
        private int x;
        private int y;

        public int getZ() {
            return z;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        public Point(int z, int x, int y) {
            this.z = z;
            this.x = x;
            this.y = y;
        }
    }

---

3. BFS 함수

• 까다롭게도 토마토의 전염은 동시에 일어난다. 이점을 유의하여 함수를 설계한다

1. 익힌 일수 ret 을 0으로 초기화
2. 큐가 비지 않을때 동안 계속 순회한다
3. 익은 토마토들은 동시에 익힌다고 가정, for loop를 통하여 루프가 끝난뒤 익힌 일수를 1 증가시킨다
4. 이미 방문한 경우를 따로 visited 배열을 지정하지 않고 숫자 1 으로 표현하여 다시 재방문 하지 않도록 한다
5. 큐에서 하나씩 좌표를 빼와서 상하좌우앞뒤로 이동후 만약 범위를 벗어나지 않는다면 큐에 담아주고 방문처리한다. 이때, 익히지 않은 토마토의 개수를 1 감소시킨다
6. 마지막으로 익히지 않은 토마토의 개수가 0이 아니라면 -1, 모두 익힐 경우 익힌 일수를 반환한다

	static int bfs(){
        int ret = 0; // 익힌 일수

        // 큐가 비지 않을때 동안 계속 순회
        while(queue.size()>0){
            // 익은 토마토들은 동시에 익힌다고 가정, for loop 를 한번 더 거친다
            int initCase = queue.size();
            for (int j = 0; j < initCase; j++) {
                Point now = queue.poll(); // 현재 토마토를 꺼내온다
                int currZ = now.getZ();
                int currX = now.getX();
                int currY = now.getY();

                // 상하좌우로 돌면서 이동 후 위치를 계산
                for (int i = 0; i < 6; i++) {
                    int nz = currZ+dz[i];
                    int nx = currX+dx[i];
                    int ny = currY+dy[i];

                    // 맵의 범위를 벗어나면 다음 방향으로 넘김
                    if (nz < 0 || nx < 0 || ny < 0 || nz >= h || nx >= n || ny >= m) continue;
                    if (graph[nz][nx][ny] == 0){
                        // 큐에 담아주고 방문처리
                        queue.add(new Point(nz,nx,ny));
                        // 토마토의 개수 -1
                        tomatoCnt--;
                        // 토마토의 방문처리
                        graph[nz][nx][ny] = 1;
                    }
                }
            }
            ret++;
        }
        if(tomatoCnt==0) return ret-1; 
        else return -1;// 모두 익히지 못한 경우, -1 반환
    }

4. 메인

	public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] graphSize = bf.readLine().split(" ");
        m = Integer.parseInt(graphSize[0]); // 가로칸의 수 y
        n = Integer.parseInt(graphSize[1]); // 세로 칸의 수 x
        h = Integer.parseInt(graphSize[2]); // 높이 h

        queue = new LinkedList<>();
        graph = new int[h][n][m];
        tomatoCnt = 0;
        // 배열값 세팅
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < n; j++) {
                StringTokenizer st = new StringTokenizer(bf.readLine());
                for (int k = 0; k < m; k++) {
                    int t = Integer.parseInt(st.nextToken());
                    if (t==0) {
                        tomatoCnt ++;
                    }
                    else if(t==1) queue.add(new Point(i,j,k)); // 1 인 경우 토마토들을 저장
                    graph[i][j][k] = t;
                }
            }
        }
        bf.close();
        if(tomatoCnt == 0) System.out.println(0); // 익혀야할 토마토가 없는경우 바로 0 반환
        else System.out.println(bfs());
    }

• 0 일 경우 익혀야할 토마토의 개수를 1증가
• 1 일 경우 큐에 토마토를 저장
• 입력을 모두 받은 이후 익혀야할 토마토가 없다면 바로 0 반환, 있다면 bfs 수행