BOJ) 토마토

토마토

7569번: 토마토

 

풀이

 

세 번을 시도한 끝에 풀었다.

처음에는 익지 않은 토마토의 총 갯수를 입력받을 때 저장하고, 매 회차 익지않은 토마토 주변을 탐색하면서 익게 만들었다.

하지만, 당연하게도 시간초과가 떴다.

 

두번째로는 익지 않은 토마토에서 시작하는 방법을 그대로 적용하고, 각 토마토 위치마다 익게되는 날짜를 저장할 int형 배열을 만들었다.

BFS 탐색을 통해서 저장한 다음, 최대 날짜를 최신화했고, 안익은 토마토가 0일로 남아있다면 불가능하다는 -1을 저장했다.

하지만, 당연하게도 시간초과가 떴다.

 

마지막으로 백조의 호수처럼 날짜에 따라 최대한 이동해야한다고 생각이 들었다.

처음 시도가 안익은 토마토에서 시작해서 생각이 협소해졌다고 생각이 들었다.

그래서 익은 토마토와 인접한 안익은 토마토로 뻗어나가면서, 익는데 걸리는 시간을 1씩 증가시키며 저장해서 통과했다.

이 로직 역시 BFS로 풀었다.

 

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    private final static int RIPE = 1, UNRIPE =0, EMPTY = -1, WAYS =6;
    private final static int[] dx = {1,-1,0,0,0,0}, dy = {0,0,1,-1,0,0}, dz = {0,0,0,0,1,-1};
    private static int m,n,h,unRipeCnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());
        int[][][] tomatoBox = new int[h][n][m];
        LinkedList<Pos> ripeList = new LinkedList<>();

        for(int i=0; i<h; i++) {
            for(int j=0; j<n; j++) {
                st = new StringTokenizer(br.readLine());
                for(int k=0; k<m; k++) {
                    int status = Integer.parseInt(st.nextToken());
                    tomatoBox[i][j][k] = status;
                    if(status == RIPE) {
                        ripeList.offer(new Pos(k,j,i,0));
                    } else if(status == UNRIPE) {
                        unRipeCnt++;
                    }
                }
            }
        }

        solution(tomatoBox, ripeList);
        br.close();
    }

    private static void solution(int[][][] tomatoBox, LinkedList<Pos> ripeList) {
        int[][][] ripeDays = new int[h][n][m];
        int day =0;

        while(!ripeList.isEmpty()) {
            Pos pos = ripeList.poll();
            for(int i=0; i<WAYS; i++) {
                int nx = pos.x+dx[i];
                int ny = pos.y+dy[i];
                int nz = pos.z+dz[i];
                int step = pos.step+RIPE; // RIPE는 익는데 걸리는 시간 1 증가의 의미로 사용

                if(isInArea(nx,ny,nz)) {
                    if(tomatoBox[nz][ny][nx] == UNRIPE && ripeDays[nz][ny][nx] == UNRIPE) { // ripeday의 UNRIPE는 아직 익지 않았다의 0으로 사용
                        ripeDays[nz][ny][nx] = step;
                        ripeList.offer(new Pos(nx,ny,nz,step));
                        day = Math.max(day, step);
                        unRipeCnt--;
                    }
                }
            }
        }
        if(unRipeCnt !=0) {
            day = EMPTY;
        }
        System.out.println(day);
    }

    private static boolean isInArea(int x, int y, int z) {
        return x>=0 && y>=0 && z>=0 && x<m && y<n && z<h;
    }

    private static class Pos {
        int x,y,z,step;
        public Pos(int x, int y, int z, int step) {
            this.x =x;
            this.y =y;
            this.z =z;
            this.step = step;
        }
    }
}