TIL(Today I Learned)

[TIL] 99클럽 코테 스터디 12일차 TIL + 백준 7569 토마토

zincah 2024. 11. 9. 00:10
반응형

 

문제 풀이

 

문제 탐색하기

너비우선탐색 알고리즘을 활용하여 문제 풀면 토마토가 모두 익을때까지 며칠이 걸리는 지 구할 수 있습니다.

익은 토마토가 있는 위치를 모두 큐에 넣어서  x축 y축 z축 모든 곳의 토마토를 탐색하여 익지 않은 토마토의 위치값을 증가시키며 다시 큐에 담습니다. (토마토는 3단 배열에 담아지게 되는데 익지 않은 토마토를 만났을 때 기존 탐색 노드 위치값 + 1로 위치값을 세팅해주면 됩니다.)

이렇게 탐색을 반복하다가 탐색이 모두 끝났을 때 익지 않은 토마토가 하나라도 있으면 -1을 출력하고 모든 토마토가 익었을 때 증가시켰던 토마토의 위치값에서 -1을 한 값을 출력해주면 토마토가 모두 익는 최소 일자를 구할 수 있습니다.

 

 

문제 풀이

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

class PointXYZ{
    int z;
    int y;
    int x;

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

public class Main {

    static int[] xArr = {-1, 0, 1, 0, 0, 0};
    static int[] yArr = {0, 1, 0, -1, 0, 0};
    static int[] hArr = {0, 0, 0, 0, 1, -1};
    static int M, N, H;
    static int[][][] arr;
    static Queue<PointXYZ> queue;

    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+1][N+1][M+1];
        queue = new LinkedList<>();

        for(int i=1; i<=H; i++){
            for(int j=1; j<=N; j++){
                st = new StringTokenizer(br.readLine());
                for(int k=1; k<=M; k++){
                    arr[i][j][k] = Integer.parseInt(st.nextToken());
                    if(arr[i][j][k] == 1){
                        queue.add(new PointXYZ(i, j, k));
                    }
                }
            }
        }

        System.out.println(bfs());
    }

    private static int bfs(){
        while(!queue.isEmpty()){
            PointXYZ point = queue.poll();
            int z = point.z;
            int y = point.y;
            int x = point.x;

            for(int i=0; i<6; i++){
                int newZ = z + hArr[i];
                int newY = y + yArr[i];
                int newX = x + xArr[i];

                if(checkPoint(newX, newY, newZ)){
                    queue.add(new PointXYZ(newZ, newY, newX));
                    arr[newZ][newY][newX] = arr[z][y][x] + 1;
                }
            }
        }

        int result = Integer.MIN_VALUE;

        for(int i=1; i<=H; i++){
            for(int j=1; j<=N; j++){
                for(int k=1; k<=M; k++){
                    if(arr[i][j][k] == 0) return -1;

                    result = Math.max(result, arr[i][j][k]);
                }
            }
        }

        return result-1;
    }

    private static boolean checkPoint(int x, int y, int z){
        if(x < 1 || x > M || y < 1 || y > N || z < 1 || z > H){
            return false;
        }

        if(arr[z][y][x] == 0){
            return true;
        }else{
            return false;
        }
    }
}

 

 

오늘의 회고

알고리즘을 파악해도 해당 알고리즘을 어떻게 활용해서 문제를 풀것인지도 중요한 것 같습니다. 오늘 문제는 아이디어를 떠오르지 않아 결국 도움을 받아 문제를 풀었는데 비슷한 문제를 여러번 풀면서 이런 패턴에도 익숙해져야할 것 같습니다ㅜㅜ..

반응형