99클럽 코테 스터디 12일차 TIL

백준 - 7569번

풀이

모든 토마토가 익는 최소 일수를 구하는 BFS 문제이다.

창고 칸에 맞게 입력된 토마토에서 익은 토마토들만 Queue에 저장한다.

BFS로 위,아래,왼쪽... 총 6 방향을 탐색하여 익지 않은 토마토 0인 경우 익은 토마토 1로 변경한다.

 

이때, 익은 토마토 1이라는 표시 대신 익은 날짜를 넣는다.

익은 토마토들로 채워진 창고를 순회하여 0이 하나라도 있으면 -1을 반환하고

0이 없다면 익은 날짜값들의 최댓값을 찾아 반환한다.

 

구현1 - 실패

문제에 높이, 가로, 세로 값이 주어졌는데도 3차원 배열이 아닌 2차원 배열을 사용했다.

개발하면서 3차원 배열까지 구현해본 적이 없어서인지 2차원 배열로도 풀 수 있을 줄 알았다.

 

탐색해야 하는 6개의 방향 중 앞, 뒤를 탐색할 때 문제가 발생했는데

창고 크기를 초기화할 때 2차원 배열로 처리하여 높이와 층이 제대로 구분되지 않은 것이 원인이었다.

// 각 층의 행과 열을 제대로 구분할 수 없다.
int[][] tomatoBoxes = new int[n * h][m];

h 값이 작게 설정되어있다면 가능할지 몰라도 값이 커질수록 구분이 어려워진다.

2차원 배열 구현 코드

 

구현2

3차원 배열을 사용하여 높이, 행, 열을 직관적으로 구분할 수 있었다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static int m, n, h;
    static int[][][] tomatoBoxes; // 3차원 배열로 변경
    static int[] dx = {1, -1, 0, 0, 0, 0};
    static int[] dy = {0, 0, 1, -1, 0, 0};
    static int[] dz = {0, 0, 0, 0, 1, -1}; // 위, 아래 이동을 위한 배열

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        m = sc.nextInt();
        n = sc.nextInt();
        h = sc.nextInt();

        tomatoBoxes = new int[h][n][m];
        Queue<Spot> queue = new LinkedList<>();

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    tomatoBoxes[i][j][k] = sc.nextInt();
                    if (tomatoBoxes[i][j][k] == 1) {
                        queue.add(new Spot(i, j, k));
                    }
                }
            }
        }

        bfs(queue);

        int result = checkDay();
        System.out.println(result);
        sc.close();
    }

    private static int checkDay() {
        int day = 0;

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    if (tomatoBoxes[i][j][k] == 0) {
                        return -1;
                    }
                    day = Math.max(day, tomatoBoxes[i][j][k]);
                }
            }
        }
        return day - 1;
    }

    static void bfs(Queue<Spot> queue) {
        while (!queue.isEmpty()) {
            Spot spot = queue.remove();
            int z = spot.z, y = spot.y, x = spot.x;

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

                if (nz >= 0 && nz < h && ny >= 0 && ny < n && nx >= 0 && nx < m) {
                    if (tomatoBoxes[nz][ny][nx] == 0) {
                        tomatoBoxes[nz][ny][nx] = tomatoBoxes[z][y][x] + 1;
                        queue.add(new Spot(nz, ny, nx));
                    }
                }
            }
        }
    }

    static class Spot {
        public int z, y, x;

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

---

백준 7569번 토마토

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