Problem Solving

[백준] 7569번: 토마토 (Java)

j h park 2024. 8. 26. 19:42

 

문제

 

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

난이도 : 골드5

 


풀이

  • 3차원 배열에서 1(익은 토마토)에 인접한 값이 0(안 익은 토마토)인 위치를 탐색해서 1로 변경해나가야 한다.
  • 탐색이 끝나는 최소 일수를 구해야 하므로 BFS를 사용하였다.
  • 시간 복잡도 : O(M * N * H)
    • 2 ≤ M, N ≤ 100, 1 ≤ H ≤ 100 이므로 최대 1,000,000으로 시간제한을 통과한다.
  • 3차원 배열이므로 x,y,z 6가지 방향으로 탐색한다.
  • 요구사항에 따라 탐색 종료 후 배열에 0(안 익은 토마토) 존재할 경우, -1을 출력하고 존재하지 않을 경우 BFS의 최대 깊이를 출력한다.

 


코드

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

public class Main{
    static int max = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        int h = Integer.parseInt(st.nextToken());
        int[][][] tomatoes = 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++){
                    tomatoes[k][j][i] = Integer.parseInt(st.nextToken());
                }
            }
        }

        bfs(tomatoes);

        for(int i=0;i<h;i++){
            for(int j=0;j<n;j++){
                for(int k=0;k<m;k++){
                    if(tomatoes[k][j][i] == 0) {
                        System.out.print(-1);
                        return;
                    }
                }
            }
        }

        System.out.print(max);
    }

    static void bfs(int[][][] tomatoes){
        Queue<Tomato> q = new LinkedList<>();
        for(int i=0;i<tomatoes.length;i++){
            for(int j=0;j<tomatoes[0].length;j++){
                for(int k=0;k<tomatoes[0][0].length;k++){
                    if(tomatoes[i][j][k] == 1) q.add(new Tomato(i, j, k, 0));
                }
            }
        }

        while(!q.isEmpty()){
            Tomato now = q.poll();

            max = Math.max(max, now.depth);

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

            for(int i=0;i<dx.length;i++){
                int newX = now.x + dx[i];
                int newY = now.y + dy[i];
                int newZ = now.z + dz[i];

                if(newX < 0 || newX >= tomatoes.length) continue;
                if(newY < 0 || newY >= tomatoes[0].length) continue;
                if(newZ < 0 || newZ >= tomatoes[0][0].length) continue;
                if(tomatoes[newX][newY][newZ] != 0) continue;

                q.add(new Tomato(newX, newY, newZ, now.depth+1));
                tomatoes[newX][newY][newZ] = 1;

            }
        }
    }

    static class Tomato{
        int x;
        int y;
        int z;
        int depth;

        Tomato(int x, int y, int z, int depth){
            this.x = x;
            this.y = y;
            this.z = z;
            this.depth = depth;
        }
    }
}