[백준] 7569번 - 토마토 (Java)(○)

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

7569번: 토마토

 

<풀이>

- 백준 7576 토마토 문제의 확장판이다. z축이 추가가되었다.

- z축(위, 그대로, 아래)가 추가가 되었으므로 6방향을 탐색해야 한다.

static int dx[] = {-1, 0, 1, 0, 0, 0};     static int dy[] = {0, 1, 0, -1, 0, 0};     static int dz[] = {0, 0, 0, 0, -1, 1};

1. 상하좌우위아래로 확산하면서 탐색하는 문제이므로 BFS 탐색 문제이다.
2. Queue에 저장할 Node class(int x, int y, int z)를 선언한다.
3. 토마토가 익으면 맵 자체의 값을 0->1로 변경한다. (방문배열 필요X)
4. BFS탐색 전에 map을 for문을 돌려서 익은 토마토의 위치를 Queue에 미리 넣고 동시에 BFS탐색을 시작하자.
5. 토마토가 익을 때마다 큐에 넣고 count+1 한다.
6. 더 이상 안익은 토마토가 없으면 탐색을 종료하고 결과를 출력한다.
7. 가지치기
   1. 맵 범위를 벗어나는 위치면 패스
   2. 이미 익은 토마토라면 패스
8. 시작전에 모든 토마토가 1이면 0출력
9. BFS탐색 종료 후에 맵을 서치해서 0이 남아있으면 -1출력

<코드구현>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
 
public class Main {
    static int M, N, H;
    static int map[][][];
    static int count = 0;
    //static boolean checked[];
    static int dx[] = {-1, 0, 1, 0, 0, 0};
    static int dy[] = {0, 1, 0, -1, 0, 0};
    static int dz[] = {0, 0, 0, 0, -1, 1};
    Queue<Node> Q = new LinkedList<>();
 
    class Node {
        int x, y, z, count;
        Node (int x, int y, int z, int count) {
            this.x = x;
            this.y = y;
            this.z = z;
            this.count = count;
        }
    }
 
    void BFS() {
        while(!Q.isEmpty()) {
            Node now = Q.poll();
            for (int i=0; i<6; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                int nz = now.z + dz[i];
                // 가지치기
                if (nx<0 || nx>=N || ny<0 || ny>=M || nz<0 || nz>=H) continue;
                if (map[nx][ny][nz] == 1) continue; // 익은 토마토면 패스
                if (map[nx][ny][nz] == -1) continue; // 빈칸이면 패스
                // 탐색성공
                map[nx][ny][nz] = 1; // 토마토 익히기
                Q.add(new Node(nx, ny, nz, now.count+1));
                count = now.count+1; // 재배일수 +1 증가
            }
        }
    }
     
    void Solve() {
        // 익은 토마토 찾아서 큐에 넣기
        for (int k=0; k<H; k++) {
            for (int i=0; i<N; i++) {
                for (int j=0; j<M; j++) {
                    if (map[i][j][k] == 1) {
                        Q.add(new Node(i, j, k, 0));
                    }
                }
            }
        }
        // (예외처리) 모든 토마토가 익었으면 0 출력 후 종료
        if (Q.size() == N*M*H) {
            System.out.println(0);
            return;
        }
        // 토마토 익히기 시작
        BFS();
        // (예외처리) 못익은 토마토 찾으면 -1 출력 후 종료
        for (int k=0; k<H; k++) {
            for (int i=0; i<N; i++) {
                for (int j=0; j<M; j++) {
                    if (map[i][j][k] == 0) {
                        System.out.println(-1);
                        return;
                    }
                }
            }            
        }

        // 결과 출력
        System.out.println(count);
    }
 
    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());//열
        N = Integer.parseInt(st.nextToken());//행
        H = Integer.parseInt(st.nextToken());//높이
        map = new int[N][M][H];
        for (int k=0; k<H; k++) {
            for (int i=0; i<N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j=0; j<M; j++) {
                    map[i][j][k] = Integer.parseInt(st.nextToken());
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }
}