99클럽 코테 스터디 12일차 TIL BFS(토마토)

https://www.acmicpc.net/problem/7569

 

<아이디어>

익은토마토로부터 6방향에 있는 안익은 토마토가 익고, 하루가 걸린다. 동시에 6방으로 퍼져야하기에 BFS로 풀었다.

안익은 토마토가 다 익는지만 확인하면 되기에 안익은 토마토 개수를 unripe 에 저장해두고 익을때마다 unripe-- 를 해주었다.

3차원 배열이고, 6개의 방향 설정만 주의해주면 된다.

q에는 익은토마토와 익혀진(?)토마토만 넣으면서 퍼트려준다.

** 익혀진 모든 토마토의 주변을 탐색하고 cnt++을 해주어야 하는 것을 주의한다

 

<제출 코드>

package STUDY.Week02;

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 Day12_BOJ_7569_토마토 {

    static class Point{
        int x, y, z;
        Point(int x, int y, int z){
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }
    static int m, n, h;
    static int unripe;
    static int cnt;
    static int[] dx = {-1, 1, 0, 0, 0, 0};
    static int[] dy = {0, 0, -1, 1, 0, 0};
    static int[] dz = {0, 0, 0, 0, -1, 1};
    static int[][][] arr;
    static Queue<Point> q;

    public static void bfs(){
        boolean[][][] visited = new boolean[h][n][m];
        while(!q.isEmpty()){
            int qSize = q.size();
            while(qSize --> 0){
                Point p = q.poll();
                for(int i=0; i<6; i++){
                    int nx = p.x + dx[i];
                    int ny = p.y + dy[i];
                    int nz = p.z + dz[i];
                    if(nx<0 || ny<0 || nz<0 || nx>=h || ny>=n || nz>=m || visited[nx][ny][nz]) continue;
                    // 안익은 토마토 만났을 때
                    if(arr[nx][ny][nz]==0) {
                        unripe--;
                        q.add(new Point(nx, ny, nz));
                    }
                    visited[nx][ny][nz] = true;
                }
            }
            cnt++;
        }
    }

    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());
        arr = new int[h][n][m];
        q = 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++){
                    arr[i][j][k] = Integer.parseInt(st.nextToken());
                    if(arr[i][j][k] == 0) unripe++;
                    if(arr[i][j][k] == 1) q.add(new Point(i, j, k));
                }
            }
        }
        // 모든 토마토 익어 있는 경우
        if(unripe==0) System.out.println(0);
        else{
            bfs();
            if(unripe==0) System.out.println(cnt-1);    // 토마토 모두 익은 상태
            else System.out.println(-1);                // 토마토 모두 익지 못하는 상태
        }
    }
}