[BOJ 7569] 토마토 (Java, 그래프 탐색)

 

 

---

문제 링크 

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

7569번: 토마토

---

풀이 

- 3차원 배열의 그래프 탐색 문제 

- 필드 초기화시 가로,세로,높이 변수가 혼란스러워 시간소요함 (그외에는 문제에서 요구하는 바와 같이 그대로 풀이하면 됨)

- multisource bfs로 토마토(1)의 위치를 찾고, 위치값을 0으로 초기화(나머지는 -1)

- 상하좌우위아래로 격자형 그래프 풀 듯이 이동하면서 위치값을 갱신하여 마지막에 최대값 찾으면 됨

- 시간 복잡도 : O(N^3), 최대 인자가 100이기때문에 Integer로 충분히 풀이 가능

 

초등부 문제라서 이 악물고 풀었다 :0
3차원 정의에서 실수가 있어서 그렇지 동일한 격자형 그래프 탐색 문제였다

---

제출 코드

import java.util.*;
import java.io.*;

public class Main {
    
    static int M, N, H;

    static int[][][] BOX;
    static int[][][] DAYS;

    static int[][] direction = {{0, 0, 1}, {0, 0, -1}, {0, 1, 0}, {1, 0, 0}, {-1, 0, 0}, {0, -1, 0}};

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken()); // 토마토 박스 번호

        DAYS = new int[N + 1][M + 1][H + 1];
        BOX = new int[N + 1][M + 1][H + 1];

        for(int k = 1; k <= H; k++) {
            for(int i = 1; i <= N; i++) { // 세로
                st = new StringTokenizer(br.readLine());
                for(int j = 1; j <= M; j++) { // 가로
                    BOX[i][j][k] = Integer.parseInt(st.nextToken());
                }
            }
        }
    }

    static void bfs() {
        Queue<Integer> que = new LinkedList<>();

        // 토마토 찾기
        for(int k = 1; k <= H; k++) {
            for(int i = 1; i <= N; i++) { // 세로
                for(int j = 1; j <= M; j++) { // 가로
                    DAYS[i][j][k] = -1;
                    if(BOX[i][j][k] == 1) {
                        que.add(i);
                        que.add(j);
                        que.add(k);
                        DAYS[i][j][k] = 0;
                    }
                }
            }
        }

        while(!que.isEmpty()) {
            int x = que.poll(), y = que.poll(), z = que.poll();

            for(int i = 0; i < 6; i++) {
                int nx = x + direction[i][0];
                int ny = y + direction[i][1];
                int nz = z + direction[i][2];

                if(nx < 1 || ny < 1 || nz < 1 || nx > N || ny > M || nz > H) continue;
                if(BOX[nx][ny][nz] != 0 || DAYS[nx][ny][nz] != -1) continue;

                que.add(nx);
                que.add(ny);
                que.add(nz);

                DAYS[nx][ny][nz] = DAYS[x][y][z] + 1;
            }
        }
    }

    static void pro() {
        bfs();

        int maxDay = 0;
        Loop1 :
        for(int k = 1; k <= H; k++) {
            for(int i = 1; i <= N; i++) { // 세로
                for(int j = 1; j <= M; j++) { // 가로
                   if(BOX[i][j][k] == 0 && DAYS[i][j][k] == -1) {
                       maxDay = -1;
                       break Loop1;
                   }

                   if(BOX[i][j][k] == 0 && maxDay < DAYS[i][j][k]) {
                       maxDay = DAYS[i][j][k];
                   }
                }
            }
        }

        System.out.println(maxDay);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}