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

1. 문제설명

토마토는 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 보관한다. 익은 토마토와 아직 익지 않은 토마토가 있고, 보관 후 하루가 지나면 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들이 익게 된다. 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향이다.

창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소일수를 구하는 문제이다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

• 시간 제한: 1초
• 메모리 제한: 256MB

 

2. 접근 방식

⇒ 최소 일자 구하기 -> BFS 사용

• 상자에 있는 토마토의 정보를 저장하는 `int[][][] box` 배열 사용한다.
• 일자를 저장하는 `int[][][] day` 배열에 토마토가 있는 위치는 0으로, 나머지는 -1로 초기화 한다.
• 토마토가 있는 위치는 큐에 추가한다.
• BFS를 사용하여 큐가 빌 때까지 (상자에 익은 토마토가 있는 경우)
  • 익은 토마토에 인접한 여섯 방향을 탐색한다.
  • 상자 범위 내에 있고, 토마토가 아직 익지 않고, 방문하지 않은 경우
    • 해당 위치의 일자(`day`)를 계산한다. (현재 위치까지의 일자 + 1)
    • 토마토를 익음 처리한다. (`box`)
    • 큐에 해당 위치를 추가한다.
• 상자에 익지 않은 토마토가 남아 있는 경우 -1 출력
• 그 외, `day` 배열에서 가장 큰 일자를 출력

 

3. 최종 코드

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

public class Main {
    static int m, n, h; // 상자의 가로&세로 칸 수, 상자 개수
    static int[][][] box; // 토마토 정보를 저장
    static int[][][] day; // 일자 저장
    static Queue<int[]> q = new ArrayDeque<>();

    static int[] dh = {-1, 1, 0, 0, 0, 0}; // 앞, 뒤
    static int[] dx = {0, 0, -1, 1, 0, 0}; // 위, 아래
    static int[] dy = {0, 0, 0, 0, -1, 1}; // 왼쪽, 오른쪽

    static void bfs() {
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for(int i=0; i<6; i++) { // 인접한 여섯 방향 탐색
                int nh = cur[0] + dh[i];
                int nx = cur[1] + dx[i];
                int ny = cur[2] + dy[i];
                // 상자 범위 내에 있는 경우
                if(nh>-1 && nh<h && nx>0 && nx<=n && ny>0 && ny<=m) {
                    // 토마토가 아직 익지 않고, 방문하지 않은 경우
                    if(box[nh][nx][ny] == 0 && day[nh][nx][ny] == -1) {
                        day[nh][nx][ny] = day[cur[0]][cur[1]][cur[2]] + 1; // 일자 계산
                        box[nh][nx][ny] = 1; // 익음 처리
                        q.add(new int[]{nh, nx, ny}); // 큐에 다음 위치 추기
                    }
                }
            }
        }
    }

    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());
        box = new int[h][n+1][m+1];
        day = new int[h][n+1][m+1];
        for(int i=0; i<h; i++) {
            for(int j=1; j<=n; j++) {
                st = new StringTokenizer(br.readLine());
                for(int k=1; k<=m; k++) {
                    box[i][j][k] = Integer.parseInt(st.nextToken());
                    day[i][j][k] = -1; // 일자 -1로 초기화
                    if(box[i][j][k] == 1) { // 토마토가 익은 경우
                        q.add(new int[]{i, j, k}); // 해당 위치를 큐에 추가
                        day[i][j][k] = 0; // 해당 위치의 일자를 0으로 설정
                    }
                }
            }
        }

        bfs();

        boolean check = true; // 토마토가 모두 익지 못할 경우를 저장
        int minDay = -1; // 최소 일자
        h: for(int i=0; i<h; i++) {
            for(int j=1; j<=n; j++) {
                for(int k=1; k<=m; k++) {
                    if(box[i][j][k] == 0) { // 상자에 안 익은 토마토가 남아있는 경우
                        check = false;
                        break h; // 최소 일자 구하는 for문을 모두 종료
                    }
                    if(day[i][j][k] > minDay) {
                        // day 배열 중 가장 큰 일자를 저장
                        minDay = day[i][j][k];
                    }
                }
            }
        }

        if(!check) System.out.println(-1);
        else System.out.println(minDay);
    }
}

 

4. 느낀점 or 기억할정보

지난 주에 풀었던 7576번 문제에서 상자의 수가 추가된 문제였다. 7576번을 풀 때는 혼자서 알고리즘 설계를 하지 못하고 결국 풀이를 찾아봤었는데, 이번에는 스스로 해결해서 뿌듯했다.

토마토 정보를 입력받을 때 BFS에서 사용할 큐에 익은 토마토 위치를 추가하고, day 배열을 이용해서 방문 처리와 일자 계산을 하는 것을 기억해내서 이번엔 혼자 풀 수 있었다.