[ 백준 ] 7576 토마토

Link | 7576번 문제 : 토마토

Solution

private static int[][][] farm;
private static int DEPTH, HEIGHT, WIDTH;

farm은 깊이 DEPTH, 세로 HEIGHT, 가로 WIDTH의 농장이다.

private static final Queue<Tomato> tomatoes = new LinkedList<>();
private static int left = 0, time = 0;

토마토가 익어가는 과정을 BFS로 계산할 때 tomatoes queue를 사용한다.
left는 아직 익지 않은 토마토의 개수이고 time은 현재 진행된 시간이다.

private static void solution() throws IOException {
    createFarm();
    plantSeeds();
    waitRipening();
    result.append(left == 0 ? time : -1);
}

Main solution method이다.
농장을 만들고 tomato를 심은 다음 익는 것을 기다린다.
모든 계산을 마치고 아직 익지 않은 토마토(left)가 있을 때는 -1을 출력하고
모든 토마토가 익었으면 익는데까지 걸린 시간을 출력한다.

private static void createFarm() throws IOException {
    StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
    WIDTH = Integer.parseInt(tokenizer.nextToken());
    HEIGHT = Integer.parseInt(tokenizer.nextToken());
    DEPTH = Integer.parseInt(tokenizer.nextToken());
    farm = new int[DEPTH + 2][HEIGHT + 2][WIDTH + 2];
}

주어진 입력값을 바탕으로 농장을 만드는데 indexOutOfRange를 대비하여 더 크게 만든다.
< 주의 >
-> 배열을 초기화하였을 때 모든 원소가 0이다.
-> 0은 익지 않은 토마토 -1은 빈칸이다.
-> 예외를 대비하여 여유분으로 추가한 배열 영역이 0이다.
-> 이대로 계산하면 여유 영역에 토마토가 있는 것으로 간주한다.
-> 전체 배열을 -1로 초기화하지 않고 -1과 0을 바꾸어서 생각한다.
-> 0 = 비어 있는 칸 / -1 = 아직 익지 않은 토마토

private static void plantSeeds() throws IOException {
    StringTokenizer tokenizer;
    for (int depth = 1; depth <= DEPTH; depth++) {
        for (int height = 1; height <= HEIGHT; height++) {
            tokenizer = new StringTokenizer(reader.readLine());
            for (int width = 1; width <= WIDTH; width++) {
                int tomato = Integer.parseInt(tokenizer.nextToken());
                if (tomato == 1) tomatoes.add(new Tomato(depth, height, width, 0));
                else if (tomato == -1) tomato = 0;
                else if (tomato == 0) {
                    left++;
                    tomato = -1;
                }
                farm[depth][height][width] = tomato;
            }
        }
    }
}

토마토들을 농장에 심는다.
익은 토마토 일 때는 tomatoes queue에 추가한다. (향휴 BFS 계산을 위하여)
빈칸일 때는 -1이 아닌 0으로 변경하여 심는다.
익지 않은 토마토일 때는 left++ 연산과 함께 0이 아닌 -1을 저장한다.

private static void waitRipening() {
    while (!tomatoes.isEmpty()) {
        Tomato tomato = tomatoes.poll();
        time = tomato.time;
        nextRipenTomato(tomato.depth + 1, tomato.height, tomato.width, tomato);
        nextRipenTomato(tomato.depth - 1, tomato.height, tomato.width, tomato);
        nextRipenTomato(tomato.depth, tomato.height + 1, tomato.width, tomato);
        nextRipenTomato(tomato.depth, tomato.height - 1, tomato.width, tomato);
        nextRipenTomato(tomato.depth, tomato.height, tomato.width + 1, tomato);
        nextRipenTomato(tomato.depth, tomato.height, tomato.width - 1, tomato);
    }
}

익은 토마토 queue tomatoes가 빌 때까지 반복한다.
꺼내온 토마토가 익기까지 걸린 시간으로 time을 업데이트한다.
익은 토마토의 상하/위아래/좌우의 토마토를 확인한다.

private static void nextRipenTomato(int depth, int height, int width, Tomato tomato) {
    if (farm[depth][height][width] == -1) {
        farm[depth][height][width] = 1;
        left--;
        tomatoes.add(new Tomato(depth, height, width, tomato.time + 1));
    }
}

확인한 토마토가 아직 익지 않은 상태라면 익은 상태로 변경한다.
또한 남은 (익지 않은) 토마토의 개수를 감소시키고 익은 토마토 queue에 추가한다.

static class Tomato {

    int depth, height, width;
    int time;

    public Tomato(int depth, int height, int width, int time) {
        this.depth = depth;
        this.height = height;
        this.width = width;
        this.time = time;
    }
}

Tomato class으로 농장에서의 위치와 익기까지의 시간을 가진다.