백준 7569

문제 개요

문제 접근 방법

1. 3차원 배열이다. -> 3차원 배열을 이용하자.
2. Look-up table 을 만들어야한다.
3. 문제를 보면 토마토가 1개 이상은 무조건 들어가 있다. -> 조건 하나 줄일 수 있다.
4. 전체 카운트를 세야한다. ->BFS가 조금 더 유리
5. 또한 문제를 보면 하루에 한번씩 카운팅 -> DFS 이용은 부적합(이건 끝까지 한큐에 달려야하니까)

package bfs_dfs;

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

/*
* 1. 문제에서 모두 익어버리는 경우를 찾는다. -> 전역 탐색이 필요하다. -> BFS / DFS 중 하나를 선택하자
* 2. 익은 토마토의 인접한 곳에 영향을 받아 익는다. -> 상하 좌우 위아래
*   2-2 Lookuptable을 만들어준다.
* 3. 배열의 가장자리를 넘어가는지 체크할 필요가 있다. 그렇기 때문에 검증할 검증 메서드가 필요하다.
*
* 모두 익은 토마토일 경우는 그냥 바로 0을 반환하라
* 익지 못하게 할 경우는 -1 반환하라
*
* 배열에는 0 (안익) / -1 (없음) / 1 (익음) 이렇게 구성되어 있다.
* 즉 검증 시 0이라면 해당 로직 탈출하는 것이 필요하다.
*
* BFS이용하는 이유
*   한싸이클을 다 돌고 난 뒤에 count가 하나 올라가야 하기 때문에 DFS에는 부적합
*
* 항상 토마토는 1개 이상은 존재한다. -> 토마토가 완전 없을 경우 배제
*
* 좌표 총 3개를 저장할 저장 공간필요 -> 클래스를 따로 구현해서 해결 필요
*   리스트도 좋지만 좀더 병확한 느낌 및 리스트가 뭔가 무겁다는 판단이 들었다
* 전체 순회를 통해 값들을 입력하고 그 이후 순회를 통해 어떤 값들이 있었는가 체크하는 로직을 통해 문제 해결 가능
* */

public class Beakjoon7569 {

    private static class PointXYZ{
        int high;
        int row;
        int col;

        public PointXYZ(int high, int row, int col) {
            this.high = high;
            this.row = row;
            this.col = col;
        }
    }

    static int M , N, H;
    static int[][][] map ;
    static StringTokenizer st;
    static Queue<PointXYZ> queue = new LinkedList<>();

    //Lookup table
    static int rowArr[] = {-1, 0, 1, 0, 0, 0};
    static int colArr[] = {0, 1, 0, -1, 0, 0};
    static int highArr[] = {0, 0, 0, 0, 1, -1};

    /*
     * 검증용 메서드부터 생성 가장 기본
     * */
    private static boolean isValid(int high, int row, int col) {
        return row >0  && col > 0 && high > 0 && col < M && row < N && high < H && map[high][row][col] == 0;
    }

    /*
    * 입력을 받는 메서드
    * */
    private static void init() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] tmp = br.readLine().split(" ");
        M = Integer.parseInt(tmp[0]) + 1;
        N = Integer.parseInt(tmp[1]) + 1;
        H = Integer.parseInt(tmp[2]) + 1;
        map = new int[H][N][M];

        for(int i = 1; i < H; i++){
            for(int j = 1; j < N; j++){
                st = new StringTokenizer(br.readLine());
                for(int k = 1; k < M; k++){
                    map[i][j][k] = Integer.parseInt(st.nextToken());
                    // bfs를 시작하는 노드를 큐에 추가
                    if(map[i][j][k] == 1){
                        queue.add(new PointXYZ(i,j,k));
                    }
                }
            }
        }
    }


    private static int BFS() {
        int result = -10;
        while (!queue.isEmpty()) {
            PointXYZ point = queue.poll();
            int high = point.high;
            int row = point.row;
            int col = point.col;

            /*
            * 사이클 다 돌린다.
            * */
            for (int i = 0; i < 6; i++) {
                int moveHigh = high + highArr[i];
                int moveRow = row + rowArr[i];
                int moveCol = col + colArr[i];

                if (isValid(moveHigh , moveRow , moveCol)) {
                    queue.add(new PointXYZ(moveHigh , moveRow , moveCol));
                    map[moveHigh][moveRow][moveCol] = map[high][row][col] + 1;
                }
            }



        }
        /*
         * 여기서 전체 탐색 결과 값을 가져와야한다.
         * */
        for(int i = 1 ; i < H ; i++){
            for(int j = 1; j <N ; j++){
                for (int k = 1; k < M; k++) {
                    if(map[i][j][k] == 0) return -1;
                    result = Math.max(result, map[i][j][k]);
                }
            }
        }
        if(result == 1) return 0;
        return result - 1;
    }

    public static void main(String[] args) throws IOException {
        init();
        int answer = BFS();

        System.out.println(answer);
    }
}

문제 특이점

이 문제를 풀면서 고민 많이 했던 것이 ArrayList를 이용해서 좌표를 적을 것인가 아니면 클래스로 만들 것인가였다.
ArrayList를 만들거나 배열을 이용해서 만든다면 생각보다 난해하고 나중에 내가 이것을 다시 봤을 때 코드 해석에 시간이 좀 걸릴 것이라고 판단했다.
그래서 클래스를 적용했다.

클래스를 적용했고 평소 하는 visit[] 배열은 딱히 필요가 없어보여서 그냥 패스했다.

문제를 풀면서 느낀점

1. 무엇이든 순서를 정형화 해야된다.
   1-1. 순서를 뒤죽박죽 했더니 배열길이 초과 에러가 엄청나게 터졌다.
   1-2. 순서 때문에 고민하는 일이 줄어든다.
2. 이쯤이면 col ,row 위치는 정확하게 알아야겠다.
3. 생각보다 이번문제는 골드 치고 쉬웠던 것 같다. 자신감이 생긴다.
4. BFS DFS에 어느정도 익숙해질 수 있었다.