[백준 / Java] 7579번 토마토

사용한 알고리즘 (BFS)

BFS

https://cobi-98.tistory.com/36

[필수 알고리즘] BFS 너비 우선 탐색 (Queue 구조) 이해

 

🔒 7579번 토마토

✔ 문제 설명

🚩 요구사항 분석

• 토마토 생성자 추가 (VO)
• int [ ][ ][] M, N, H 상자(box) 생성
• 상하좌우로 이동할 수 있는 배열(dx, dy, dz) 생성
• 익은 토마토 queue에 추가
• 큐가 빌 때까지 반복
  
  • 이동할수 있는 경로(상자에 벗어나지 않는 경우)
  • 상하좌우 + 위아래를 확인해 익지 않은 토마토라면 해당 토마토를 익게 만든다.
  • 그 토마토의 위치를 queue 추가
  • 날짜 ++;
• queue가 다 비었을 때 안 익은 토마토가 있다면 -1

 

 

🔑 문제풀이

해당문제는 토마토 상자 하나를 풀었다면, 쉽게 풀었을 문제이다.

https://cobi-98.tistory.com/38

 

요구사항을 분석한 대로 queue에 익은 토마토를 넣는다.  

queue에 담겨져있는 현재 익은 토마토의 해당 위치를 꺼내서  상하좌우 + 위, 아래를 체크한다.

 

아직 익지 않은 토마토가 있다면,

토마토의 위치를 큐에 추가

토마토 날짜(day)  + 1 증가

 

큐가 비어져서 상자의 (토마토를 다 익게 만들었다면)

토마토상자 전체를 다시 돌면서 익지 않은 토마토가 있다면 -1을 출력, 없다면 day 날짜를 출력

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static class tomato2 {
        int x;
        int y;
        int z;
        int day;

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

    public static int M;
    public static int N;
    public static int H;
    public static int[][][] map;
    public static int day;

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

    public static Queue<tomato2> 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());

        map = new int[M][N][H];
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < N; j++) {
                st = new StringTokenizer(br.readLine());
                for (int k = 0; k < M; k++) {
                    map[k][j][i] = Integer.parseInt(st.nextToken());

                    if (map[k][j][i] == 1) {
                        queue.offer(new tomato2(k, j, i, 0));
                    }
                }
            }
        }

        bfs();
    }

    public static void bfs() {

        while (!queue.isEmpty()) {
            tomato2 t = queue.poll();
            day = t.day;

            for (int i = 0; i < 6; i++) {
                int nx = t.x + dx[i];
                int ny = t.y + dy[i];
                int nz = t.z + dz[i];

                if (nx >= 0 && ny >= 0 && nz >= 0 && nx < M && ny < N && nz < H) {
                    if (map[nx][ny][nz] == 0) {
                        map[nx][ny][nz] = 1;
                        queue.add(new tomato2(nx, ny, nz, day + 1));

                    }
                }
            }
        }

        if (!tomatoCheck()) {
            System.out.println(-1);
        } else {
            System.out.println(day);
        }
    }

    public static boolean tomatoCheck() {
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < M; k++) {
                    if (map[k][j][i] == 0) {
                        return false;
                    }
                }
            }
        }

        return true;
    }

}