[백준 7569] 토마토 (JAVA)

백준 7569번 문제 - 토마토

7569번: 토마토

---

문제 분석

 

 

 

• 창고에 토마토가 격자모양의 상자들에 보관되어있다.
• 익은 토마토는 하루가 지나면 인접한 곳에 있는 토마토도 익게 한다.
  • 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미
• 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 
  • 익은 토마토 : 1
  • 익지 않은 토마도 : 0
  • 토마토 없음 : -1 (일부 칸에는 토마토가 들어있지 않을 수도 있다.)

---

해결 키 포인트

 

• BFS 문제
• 익은 토마토들을 리스트로 제작한다.
  • ArrayList<Location> ripeTomato = new ArrayList<>();
• ripeTomato에 담겨져있는 위치 정보를 Queue에 넣는다.
  • 위치 정보 x,y,z를 가지고 있는 Location 클래스
• 근처 토마토 확인 후 안익었으면 Queue에 삽입

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 < 6; i++) {
    int x = l.x + dx[i];
    int y = l.y + dy[i];
    int z = l.z + dz[i];
    if (x >= 0 && x < M && y >= 0 && y < N && z >= 0 && z < H
        	&& tomato[x][y][z] == 0 && !visited[x][y][z]) {
        queue.add(new Location(x, y, z));
        tomato[x][y][z] = 1;
        visited[x][y][z] = true;
    }
}

 

• 토마토 배열에 0이 없는지 체크 (익지 않은 토마토가 없는지)
• 큐에 담겨져 있는 모든 Location을 확인했을 경우 count 증가

---

 

코드

 

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

public class Main {
    public static int M,N,H;
    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());

        int [][][] tomato = new int[M][N][H];
        ArrayList<Location> ripeTomato = new ArrayList<>();

        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++) {
                    tomato[k][j][i] = Integer.parseInt(st.nextToken());
                    // 익은 토마토 기억
                    if(tomato[k][j][i] == 1) {
                        ripeTomato.add(new Location(k,j,i));
                    }
                }
            }
        }

        System.out.println(BFS(ripeTomato, tomato));
    }

    static public int BFS(ArrayList<Location> ripe, int [][][] tomato) {
        int count = 0;
        Queue<Location> queue = new LinkedList<>();
        boolean [][][] visited = new boolean[M][N][H];

        // 익은 토마토 큐에 삽입
        for (int i = 0; i < ripe.size(); i++) {
            Location l = ripe.get(i);
            queue.add(l);
            visited[l.x][l.y][l.z] = true;
        }

        // 근처 토마토 확인을 도와줄 변수
        int [] dx = {1,-1,0,0,0,0};
        int [] dy = {0,0,1,-1,0,0};
        int [] dz = {0,0,0,0,1,-1};

        // 큐가 빌 때까지
        while (!queue.isEmpty()) {
            int queueSize = queue.size();

            // 들어있는 값 다 확인
            for (int q = 0; q < queueSize; q++) {
                Location l = queue.poll();

                // 좌우상하 위 아래 다 확인
                for (int i = 0; i < 6; i++) {
                    int x = l.x + dx[i];
                    int y = l.y + dy[i];
                    int z = l.z + dz[i];
                    if (x >= 0 && x < M && y >= 0 && y < N && z >= 0 && z < H
                            && tomato[x][y][z] == 0 && !visited[x][y][z]) {
                        queue.add(new Location(x, y, z));
                        tomato[x][y][z] = 1;
                        visited[x][y][z] = true;
                    }
                }
            }
            count++;
        }

        // 모든 토마토가 익었는지 확인
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < M; k++) {
                    // 안익었을 경우 return -1
                    if(tomato[k][j][i] == 0)
                        return -1;
                }
            }
        }

        // 모두 익었을 경우, return count - 1 (큐에서 모두 뺄 때도 count가 증가하므로)
        return count-1;
    }

    public static class Location {
        int x, y, z;
        public Location(int x, int y, int z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }

}