백준 토마토 7569 java

문제링크

문제접근

• bfs를 3차원 배열로 돌리면 되겠다
• 3차원 배열이라 조금 헷갈리지만 문제 없어보임
• map[H][N][M]
• que.size()로 턴 개념 적용시켜서 몇일 걸리는지 체크

코드

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

public class baek_7569 {
    static int Count0 = 0;
    static int Count1 = 0;
    static int M,N,H;
    static Queue<Tomato> que = new LinkedList<>();
    static int[][][] map;
    static boolean[][][] visit;
    static int[] di = {1,-1,0,0,0,0};
    static int[] dj = {0,0,1,-1,0,0};
    static int[] dk = {0,0,0,0,1,-1};
    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());
        map = new int[H][N][M];
        visit = new boolean[H][N][M];
        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++){
                    int now = Integer.parseInt(st.nextToken());
                    map[h][n][m] = now;
                    if(now == 0) Count0++;
                    else {
                        if(now == 1) {
                            que.add(new Tomato(n,m,h));
                            Count1++;
                        }
                        visit[h][n][m] = true;
                    }
                }
            }
        }
        bfs();
    }
    private static void bfs(){
        if(Count0 == 0){
            System.out.println(0);
            return;
        }
        else if(Count1 == 0){
            System.out.println(-1);
            return;
        }
        int day = 0;
        while(!que.isEmpty()){
            int size = que.size();
            for(int s=0;s<size;s++){
                Tomato nowT = que.poll();
                for(int d=0;d<6;d++){
                    int nexti = nowT.i + di[d];
                    int nextj = nowT.j + dj[d];
                    int nextk = nowT.k + dk[d];
                    if(nexti<0 || nexti>=N || nextj<0 || nextj>=M ||nextk<0 || nextk>=H || visit[nextk][nexti][nextj]) continue;
                    else if(map[nextk][nexti][nextj] == 0 && !visit[nextk][nexti][nextj]){
                        que.add(new Tomato(nexti,nextj,nextk));
                        Count0--;
                        visit[nextk][nexti][nextj] = true;
                    }
                }
            }
            day++;
            if(Count0 == 0) break;
        }
        if(Count0 == 0){
            System.out.println(day);
        }
        else{
            System.out.println(-1);
        }
    }
    public static class Tomato{
        int i;
        int j;
        int k;
        public Tomato(int i,int j, int k){
            this.i = i;
            this.j = j;
            this.k = k;
        }
    }
}

결과

정리

• 3차원 배열에서 BFS
• 주의할 점은 N,M,H가 배열에서 어디인지 [H][N][M]
• 또 Tomato 클래스 만든거에서 i,j,k = N,M,H
• BFS 감을 많이 되살렸다