[백준] 7569 - 토마토

Solved.ac Class 완전정복 프로젝트

Class : 3 ~ 3 ++

 

---

링크

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

7569번: 토마토

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

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

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

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

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

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

접근방법

 저번 7576번의 3D 버전이다. 익은 토마토가 하루마다 6방향으로 주변 토마토를 익게 만들 때, 모든 토마토가 익는데 걸리는 시간을 구하는 문제이다. 단, 모두 익지 못할 경우엔 -1을 반환해야 한다. 해당 문제를 풀기 위해서는 시간이 지날수록 비약적으로 늘어나는 토마토의 개수를 어떻게 처리해야 할지에 대해 고민해야 한다. 충분히 고민한 뒤 풀이로 들어가자.

 

풀이

 하루마다 각 토마토에서 6가지 방향으로 전이가 일어난다. 이러한 하루 단위의 방식은 BFS의 형식과 유사하다. 하나의 익은 토마토가 존재했다면, 다음날은 6개 이하의 인접토마토가 익을 것이다.(6개 이하인 이유는 이미 익었거나, 상자의 구석에 있는 경우를 고려한 것이다.) 첫날은 최대 6개의 인접 토마토만을 신경 쓰면 되었지만, 둘째 날부터는 최대 36개의 인접 토마토를 고려해야 한다. 무려 단 하나의 토마토에 대해서 말이다. 따라서 1) 하루 단위를 나누는 방법과 하루 단위로 나누었을 때, 2) 전이될 수 있는 토마토의 개수를 구하는 두 가지 함수가 필요하다. 말이 어렵지 코드로 풀어보면 전혀 어렵지 않다.

 

1) 하루 단위로 나누는 방법

 일반적인 BFS를 통해 이 문제를 해결하려고 하면, 어디서 부터가 다음날인지 구별하기가 난해하다. 이를 해결하기 위한 방법으로 본인은 임시 큐를 하나 생성했다. BFS알고리즘은 Queue에 데이터가 빌 때까지 너비탐색을 진행하게 되는데, 일반적으로 완전탐색을 할 때 까지 큐 뒤편에서 데이터가 들어므로, 임시 큐를 만들어 이 부분을 잠시 멈춰 준다. 그리고 날짜를 카운트 한 뒤, 임시 큐에 있던 큐를 원래 큐로 바꿔주고, BFS를 진행하면, 하루 단위로 끊어서 구현할 수 있다.

 

2) 전이될 수 있는 토마토의 개수를 확인하는 방법

 기준 토마토의 6방향을 전부 확인하면 된다. 단, 상자의 크기를 초과하거나, 썩은 토마토, 이미 익은 토마토를 제외하면 개수를 확인할 수 있다.

 

코드

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

    public static void main(String[] args) throws IOException {
        Main test = new Main();
    }

    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        Queue<Demension> lst = new LinkedList<>();
        int col = Integer.parseInt(stk.nextToken());
        int row = Integer.parseInt(stk.nextToken());
        int height = Integer.parseInt(stk.nextToken());

        int[][][] arr = new int[height][row][col];
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < row; j++) {
                stk = new StringTokenizer(br.readLine()," ");
                for (int k = 0; k < col; k++) {
                    arr[i][j][k] = Integer.parseInt(stk.nextToken());
                    if(arr[i][j][k] ==1){
                        lst.add(new Demension(i,j,k));
                    }
                }
            }
        }

        int result = solution(arr,lst);
        System.out.println(result);

    }

   
    private int solution(int[][][] arr,Queue<Demension> lst ) {
        
        int day = 0;
        while (!lst.isEmpty()){
		//해당 큐가 빌때까지 모았다가 다시 큐에 넣음
            lst = new LinkedList<>(infection(lst,arr));
            day++;

        }

        if (isClear(arr)){
            return day-1;
        }
        return -1;


    }


    //전채가 다 감염되었는지 확인
    private boolean isClear(int[][][] arr){

        for (int[][] square : arr){
            for(int[] line : square){
                for (int atom : line){
                    if(atom == 0){
                        return false;
                    }

                }
            }
        }

        return true;
    }
    
    //하루가 지날때마다 주변 점염
    private Queue<Demension> infection(Queue<Demension> lst,int[][][] arr){

        Queue<Demension> copied = new LinkedList<>();
        while (!lst.isEmpty()){
            Demension cur = lst.poll();


            int[][] ways = {{1,0,0},
                    {-1,0,0},
                    {0,1,0},
                    {0,-1,0},
                    {0,0,1},
                    {0,0,-1}};

            for (int i = 0 ; i < ways.length ; i++){

                int next_x = cur.x + ways[i][0];
                int next_y = cur.y + ways[i][1];
                int next_z = cur.z + ways[i][2];

                //범위 안에있을 때만
                if (next_x>= 0 && next_x < arr.length && next_y>= 0 && next_y < arr[0].length && next_z >=0 && next_z< arr[0][0].length){
                    if( arr[next_x][next_y][next_z] == 0){
                    //임시 큐를 이용하여, 큐에 들어가야할 값들을 여기에 넣는다.
                        copied.add(new Demension(next_x,next_y,next_z));
                        arr[next_x][next_y][next_z] = 1;

                    }
                }
            }



        }
        //임시 큐 반환
        return copied;
    }


    class Demension{
        Integer x;
        Integer y;
        Integer z;

        public Demension(Integer x, Integer y, Integer z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }

}

결과

 

 저번 문제에서는 모든 토마토를 익게 할 수 있는지 없는지에 대해 확인 후에 날짜를 카운트하도록 구현했는데, 이번 문제를 통해 그것이 더 비효율적이라는 것을 깨달았다. 최악의 경우를 고려할 때, 훨씬 더 오래 걸린다. 따라고 코드를 제거하고 일관된 처리로 변경했다. 이 코드가 더 깔끔하다고 생각이 든다.

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.