[백준] 토마토 : 7569 : Java - BFS (S1)

1.  💎 문제

7569번: 토마토

 

• 익은 토마토는 1일이 지나면 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 익힌다.
• 토마토가 모두 익을 때까지 최소 며칠이 걸리는지 출력한다.
• 모두가 익지 못하는 상황이면 -1을 출력하고 처음부터 모든 토마토가 익어있으면 0을 출력한다.

 

---

 

2.  🤔 어떻게 풀까

저번에 2차원 상자에 있는 유사한 토마토 문제를 풀어봐서 바로 BFS로 풀면되겠구나 하고 풀었다.

추가된 것은 바로 좌표가 3차원이 된 것! 그래서 3차원 배열을 쓰기로 했다.

 

하지만,, 구현 생각없이 무작정 덤벼든 문제는 오랜 시간이 걸리는 것을 또 잊었다,,

하다보니 예상치 못했던 문제들과 대충 설정한 변수들 때문에 여러 번 고쳤고 푸는데 오랜시간이 걸렸다.

 

풀었던 방법의 핵심은 바로 처음부터 익은 토마토를 모두 큐에 넣는 것이다. 그런다음 지난 일 수(count)를 점점 증가시키면서 탐색을 끝낸다. 가장 마지막 요소의 count가 바로 모든 토마토가 익을 때까지 걸리는 일이다. 간단할 수도 있는 BFS 문제이다. 하지만 3차원 좌표를 이용한다는 점과 익은 토마토를 모두 넣어놓는 생각을 못하면 아주 돌아가게된다😅.. 

 

3. 아쉬운 점 & 배운 점

1. 3차원 좌표는 높이 변수가 가장 앞에 & (x,y,z) 변수 사용 지양

내가 사용한 방법은 x, y, z 순으로 무작정 쓰는 것이었다. 하지만 그러다보니 x,y부터 배열로 치환하면 y는 세로줄, x는 가로줄을 가리켜야 하기 때문에 (2,1)의 좌표는 배열로 nums[1][2]가 되어 순서가 바뀐다. 그러다보니 nums[y][x] 순으로 사용해야 올바른 x,y 좌표가 되지만 반대로 생각하니 힘들다. 그러므로 무조건 좌표라고 x, y, z표기를 쓰는 것을 지양하는 것이 좋으며, 상황에 따라 적절한 이름을 사용한다.

 

또한 높이를 나타내는 z를 맨 뒤에쓰니 디버깅 했을 때 배열의 형체를 해석하는게 매우 힘들었다. z를 맨 앞에 써야 층별로 상자를 나눈 것처럼 편하게 볼 수 있다. 이를 종합할 때 높이를 나타내는 요소는 가장 첫번째 배열에 써야하고, 문제에 맞는 변수명을 통해 접근하자! 이번 문제같은 경우 `nums[z][y][x]` ➡️ `nums[height][row][col]`과 같이 row, col를 쓰도록 하자.

 

 

2. BFS라고 visited 여부만 체크해서 하는게 아니다.

마냥 BFS라서 탐색의 종료를 방문 여부로 체크한 것과, 익은 토마토를 발견하면 그때 새로운 BFS 탐색을 진행하여 틀렸었다. 이 문제처럼 동시에 일어나는 문제는 큐에 모두 넣어놓고 시작해야 한다. 이것처럼 모든 문제는 구상을 하고 문제를 풀자

 

 

3. 범위 체크하기 귀찮다고 여유 공간으로 만들지 말자.

나는 탐색마다 유효 범위 체크가 귀찮아 주로 주어진 크기보다 2만큼 크기를 더 설정하여, 변수를 만들어 index 범위 초과 에러가 안나도록 하고 있었다. 하지만 이번 문제를 풀면서 느낀 것은 공간이 더 생기니깐 신경써야할 부분이 더 늘어난다는 것이다. 딱 맞게 만들어서 범위를 잘 체크하도록 하자! 얼마 되지도 않는다.

 

 

 

4.  🖥️ 코드

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

public class Main {
    static int [][][] tomato;
    static Queue<Position> tomatos;
    static int N;
    static int M;
    static int H;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st=  new StringTokenizer(br.readLine());
        // 가로 칸
         M = Integer.parseInt(st.nextToken());
        // 세로 칸
         N = Integer.parseInt(st.nextToken());
        // 높이
         H = Integer.parseInt(st.nextToken());

        tomato = new int[H][N][M];
        // 확인해야할 총 토마토 개수
        int goal = M*N*H;

        // 토마토 입력
        boolean isFull = true;
        tomatos = new LinkedList<>();

        for(int z =0; z<H; z++){
            for(int r=0; r<N; r++){
                st = new StringTokenizer(br.readLine());
                for(int c=0; c<M; c++){
                    tomato[z][r][c] = Integer.parseInt(st.nextToken());
                    if(tomato[z][r][c] == -1){
                        goal--;
                    }
                    // 익은 토마토 넣기
                    if(tomato[z][r][c] == 1){
                        tomatos.add(new Position(r,c,z, 0));
                    }
                }
            }
        }

        int now = 0;
        int time = 0;
        int dx [] = {0,1,0,-1,0,0};
        int dy [] = {1,0,-1,0,0,0};
        int dz [] = {0,0,0,0,1, -1};

        while(!tomatos.isEmpty()){
            Position curPosition = tomatos.poll();
            time = curPosition.count;
            now++;
            for(int i=0; i<dx.length; i++){
                int nextX = curPosition.x + dx[i];
                int nextY = curPosition.y + dy[i];
                int nextZ = curPosition.z + dz[i];

                if(isRange(nextX,nextY,nextZ)) {
                    // 안 익은 토마토라면 추가
                    if(tomato[nextZ][nextX][nextY] == 0){
                        tomato[nextZ][nextX][nextY] = 1;
                        tomatos.add(new Position(nextX, nextY, nextZ, time+1));
                    }
                }
            }
        }

        // 결과 확인
        if(now == goal){
            bw.write(Integer.toString(time));
        } else{
            bw.write(Integer.toString(-1));
        }

        bw.flush();

        bw.close();
        br.close();
    }


    public static boolean isRange(int x, int y, int z){
        if(x>=0 && x<N && y>=0 && y<M && z>=0 && z<H)
            return true;
        return false;
    }
}

class Position{
    int x;
    int y;
    int z;
    int count;

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