[백준 7569] 토마토 문제 풀이(JAVA)

문제는 다음 링크를 통해 볼 수 있다

7569번: 토마토

 

문제 풀이

---

 이번 문제는 dfs문제이다 익은 토마토가 있는 위치에서 위, 아래, 왼쪽, 오른쪽, 앞, 뒤중 익지 않은 토마토를 찾아 익은 토마토로 바꿔주면 되는 문제이다. 간단한 순서는 다음과 같다.

1. 현재 익은 토마토의 위치를 큐에 모두 저장한다
2. 큐의 사이즈를 저장한다
3. 큐에서 익은 토마토 위치 하나를 꺼내고
   해당 위치로부터 익힐 수 있는 토마토의 위치를 큐에 넣고 익은 토마토로 변경한다.
4. 3번을 2에서 정한 큐의 사이즈만큼 반복한다.
5. 2~4번 과정을 큐가 빌 때까지 진행한다

 

 

 이번 문제를 풀기 위해서 큐를 사용하였다. 처음 입력을 받을 때 큐에 익은 토마토의 위치 정보를 저장해준다. 그러면 큐에는 익은 토마토의 위치가 들어가게 된다. 이제부터 큐가 빌 때까지 while문을 돌면서 익은 토마토 주위에 익지 않은 토마토를 익은 토마토로 바꿔준다. whille문 안에서는 for문을 이용하여 큐의 사이즈 크기의 for문이 1번 돌면 하루가 지난 것을 표현한다. 처음에는 -1일차로 설정한다. 처음 for문을 돌 때는 큐 안에 있는 익은 토마토를 확인하고 익힐 수 있는 토마토는 익혀준다. 익힐 수 있는 토마토는 이후 다른 토마토도 익힐 수 있기 때문에 queue에 넣어준다. 이렇게 1번의 for문을 돌면 하루가 지나는 것이다. 초기값을 -1일차로 설정한 이유는 익힐 수 있는 토마토가 없을 때도 for문을 돌기 때문이다. 예를 들어 상자 안에 익은 토마토들로만 들어있다면 처음 큐에 모든 토마토의 위치가 들어가게 된다. 그리고 while문 안에 for문을 한번 돌면 하루가 지나게 된다. 그러나 문제에서는 토마토를 바꿀 수 없는 경우는 0일차로 표기하게 되었기 때문에 -1부터 시작한다.

 

코드

---

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");


        // M, N, H 입력
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int H = Integer.parseInt(st.nextToken());

        // 높이, 세로, 가로
        int[][][] boxes = new int[H][N][M];

        Queue<int[]> q = new LinkedList<>();

        for (int h = 0; h < H; h++) {
            for (int n = 0; n < N; n++) {
                st = new StringTokenizer(br.readLine(), " ");
                for (int m = 0; m < M; m++) {
                    boxes[h][n][m] = Integer.parseInt(st.nextToken());
                    if (boxes[h][n][m] == 1) {
                        q.offer(new int[]{h, n, m});
                    }
                }
            }
        }

        // 오늘 익은 토마토의 개수
        int count = q.size();
        int day = -1;
        while (!q.isEmpty()) {
            for (int i = 0; i < count; i++) {
                int[] polled = q.poll();

                int h = polled[0];
                int n = polled[1];
                int m = polled[2];

                // h 변화
                if (h + 1 < H && boxes[h + 1][n][m] == 0) {
                    q.offer(new int[]{h + 1, n, m});
                    boxes[h + 1][n][m] = 1;
                }
                if (h - 1 >= 0 && boxes[h - 1][n][m] == 0) {
                    q.offer(new int[]{h - 1, n, m});
                    boxes[h - 1][n][m] = 1;
                }

                // n 변화
                if (n + 1 < N && boxes[h][n + 1][m] == 0) {
                    q.offer(new int[]{h, n + 1, m});
                    boxes[h][n + 1][m] = 1;
                }
                if (n - 1 >= 0 && boxes[h][n - 1][m] == 0) {
                    q.offer(new int[]{h, n - 1, m});
                    boxes[h][n - 1][m] = 1;
                }

                // m 변화
                if (m + 1 < M && boxes[h][n][m + 1] == 0) {
                    q.offer(new int[]{h, n, m + 1});
                    boxes[h][n][m + 1] = 1;
                }
                if (m - 1 >= 0 && boxes[h][n][m - 1] == 0) {
                    q.offer(new int[]{h, n, m - 1});
                    boxes[h][n][m - 1] = 1;
                }
            }

            count = q.size();
            day++;
        }

        boolean flag = true;

        for (int h = 0; h < H && flag; h++) {
            for (int n = 0; n < N && flag; n++) {
                for (int m = 0; m < M && flag; m++) {
                    if (boxes[h][n][m] == 0) {
                        flag = false;
                        day = -1;
                    }
                }
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(day));
        bw.flush();
        bw.close();


    }
}

 

주의할 점

---

처음 문제를 풀었을 때는 메모리 초과가 나왔다. 처음에는 배열이나 큐가 메모리 초과가 날만큼 큰 계산이 없는데 왜 나는지 알 수 없었다. 백준 질문 게시판에서 똑같은 문제가 있는 사람이 있었고 답변은 if문 안에서 토마토를 익었다고 표시해야 한다는 것이였다. 처음에는 왜 그런지 잘 몰랐는데 처음 로직이었던 토마토를 큐에서 꺼내면서 익힘 표시를 할 경우, 중복해서 큐에 들어가는 문제가 발생할 수 있다. 예를 들어 

1, 0

0, 1

이런 형식으로 주어진다면 왼쪽 위 1이 익힐 수 있는 토마토는 (0, 1), (1, 0)이고 오른쪽 아래도 동일하다. 이때 토마토를 큐에서 꺼냈을 때 1로 바꾸게 되면 위 코드의 조건식에서 중복을 걸러내지 못한다. 큐에 넣는 과정에서 1로 바꿔주면 오른쪽 아래에서 익힐 수 있는 토마토를 넣을 때 if문 조건에 걸리지 않기 때문에 중복된 토마토는 제거하고 넣을 수 있다.