[Algorithm] 백준_토마토_7569번 (JAVA) 🍅

📝문제

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

토마토 7569

티어 : Gold 5

 

💡풀이

문제 유형

너비우선 탐색

 

걸린시간

거의 60분

 

시간 복잡도

O(H×N×M)

 

풀이 방법 도출

1. 처음에 dfs로 접근하다가 최솟값 구하는 문제라 bfs로 방향을 틀었다. dfs로 30분 날린듯
2. tomato = new int[H][N][M]; 토마토가 들어있는 3차원 배열을 선언하고 입력값을 차례대로 넣어주었다.
3. 이때 모든 토마토가 익어있는 상황을 확인하기 위해 boolean completed = true; 변수를 활용하였다. 0을 반견하면 false로 바꿔주고 completed = true면 조기 종료 해주었다.
4. 이후 익은 토마토를 발견하면 토마토의 위치와 day를 큐에 넣어준다.
5. bfs 함수를 선언하여 익은 토마토 주변으로 0인 값에 대해 탐색을 진행한다.
6. 이때 day는 큐에서 나온 값으로 저장해둔다.
7. 탐색이 끝난 후에도 0인 값이 있다면 토마토가 모두 익지는 못하는 상황이므로 -1을 출력하고 0이 없다면 day를 출력해준다

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

class Main {
    static int day;
    static int N, M, H;
    static int[][][] tomato;
    static boolean[][][] visited;
    static Queue<Node> queue = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        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());
        tomato = new int[H][N][M];
        visited = new boolean[H][N][M];

        boolean completed = true;
        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++) {
                    tomato[k][i][j] = Integer.parseInt(st.nextToken());
                    if(tomato[k][i][j] == 0){
                        completed = false;
                    }
                }
            }
        }

        if(completed){//모든 토마토가 익어있는 상황
            System.out.println(0);
            return;
        }

        //1:익은 토마토, 0:익지 않은 토마토, -1:x
        for (int k = 0; k < H; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (!visited[k][i][j] && tomato[k][i][j] == 1) {
                        visited[k][i][j] = true;
                        queue.add(new Node(k, i, j, 0)); //익은 토마토들을 집어넣음
                    }
                }
            }
        }
        bfs();
        boolean raw = false;
        for (int k = 0; k < H; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (tomato[k][i][j] == 0) {//토마토가 모두 익지 못하는 상황
                        raw = true;
                        break;
                    }
                }
            }
        }
        System.out.println(raw ? -1 : day);
    }

    public static void bfs() {
        int[] dn = {0, 1, 0, -1, 0, 0};
        int[] dm = {1, 0, -1, 0, 0, 0};
        int[] dh = {0, 0, 0, 0, 1, -1};
        day = 0;

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            int h = node.h;
            int n = node.n;
            int m = node.m;
            day = node.day;

            for (int i = 0; i < 6; i++) {
                int dn_n = n + dn[i];
                int dm_m = m + dm[i];
                int dh_h = h + dh[i];

                if (dn_n >= 0 && dn_n < N && dm_m >= 0 && dm_m < M && dh_h >= 0 && dh_h < H) {
                    if (!visited[dh_h][dn_n][dm_m] && tomato[dh_h][dn_n][dm_m] == 0) {
                        visited[dh_h][dn_n][dm_m] = true;
                        tomato[dh_h][dn_n][dm_m] = 1;
                        queue.add(new Node(dh_h, dn_n, dm_m, day + 1));
                    }
                }
            }
        }
    }
}

class Node {
    int h;
    int n;
    int m;
    int day;

    public Node(int h, int n, int m, int day) {
        this.h = h;
        this.n = n;
        this.m = m;
        this.day = day;
    }
}

 

🤔Review

2차원 배열의 탐색 문제만 풀다가 3차원 배열의 탐색은 처음이라 낯설었지만 그래도 해냄✌️

dfs나 bfs는 유형이 딱 정해져있어서 편하다..다른 알고리즘에 비하면 효자 알고리즘이 따로 없다