[백준] Q7569_토마토

✨Link Q7569_토마토

🤔 문제

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.
토마토가 하나 이상 있는 경우만 입력으로 주어진다.
예제입력--->
5 3 1
0 -1 0 0 0
-1 -1 0 1 1
0 0 0 1 1

출력

여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
예제출력 --->
-1

💡 접근

Q5676_토마토 문제와 풀이가 비슷했다. 높이만 추가 되니까 2차원 배열에서 3차원 배열로 만들어 준다. 그 외에는 동일하다.

💻 코드(1)_나의 풀이

import org.w3c.dom.Node;

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 Q7569 {

    static int[][][] map;//3차 배열 사용
    static int h,n,m;
    static int day = 0;
    static Queue<Node> queue;
    static int[] dh={0,0,0,0,-1,1};
    static int[] dx={-1,0,1,0,0,0};
    static int[] dy={0,1,0,-1,0,0};

    static class Node{
        int z,x,y;
        int day;

        public Node(int z, int x, int y, int day){
            this.z=z;
            this.x=x;
            this.y=y;
            this.day=day;
        }
    }

    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];

        queue = new LinkedList();

        for(int i=0;i<h;i++){//높이가 추가되면서 3중 for문 사용
            for(int j=0;j<n;j++){
                st=new StringTokenizer(br.readLine());
                for(int k=0;k<m;k++){
                    map[i][j][k] = Integer.parseInt(st.nextToken());
                    if(map[i][j][k]==1){
                        queue.offer(new Node(i,j,k,0));//0일째 익은 토마토들을 큐에 담기(초기화)
                    }
                }
            }
        }

        bfs();

        for(int i=0;i<h;i++){
            for(int j=0;j<n;j++){
                for(int k=0;k<m;k++){
                    if(map[i][j][k]==0){//익지 않은 토마토가 있다면
                        System.out.println(-1);
                        System.exit(0);
                    }
                }
            }
        }
        System.out.println(day);//마지막으로 익은 토마토 day(제일 큰)값
    }

    public static void bfs(){
        while(!queue.isEmpty()){
            Node node = queue.poll();
            for(int i=0;i<6;i++){
                int z = node.z+dh[i];
                int x = node.x+dx[i];
                int y = node.y+dy[i];
                if(z>=0&&z<h && x>=0&&x<n && y>=0&&y<m){
                    if(map[z][x][y]==0){//인접 토마토가 익지 않은 토마토일때
                        queue.add(new Node(z,x,y,node.day+1));//다음날
                        map[z][x][y]=1;
                        day = Math.max(day,node.day+1);
                    }
                }
            }
        }
    }
}

  • 높이가 추가되면서 3차배열, 3중포문을 사용했다. 풀이방법은 Q5676_토마토와 동일하다!

좋은 웹페이지 즐겨찾기