[자바] 백준 7576번 토마토 2021-06-23

우선 어떤 알고리즘을 풀어서 해를 낼수 있겠다. 이런 느낌은 5초만에 바로 올정도로 접근법은 쉽지만, 구체적인 해답 경로를 찾기에는 어려웠다. 아니, 어렵다기 보다는 신박? 했다 해야하나... 우선 기존 BFS문제와는 조금 결이 달랐다. 기존 문제는  각문제마다 조건이나 상황이 다 다르겠지만, '어느 지점까지 도착할지 최솟값을 구하여라' 이런 류가 대부분이였다. 그러나 이 문제는 한 계층마다 같은 값을 더해준다는 느낌(한번 이동을 수행할때마다)은 BFS문제들과 같은데, 2가지 내 머릿속의 문제점을 해결하지 못하여서 쉽게 코드를 짜지 못하고 있었다.

 

내가 문제를 풀면서 마주했던 의문점.

 

1.어느곳이 마지막 도착점인지, 또한 무엇보다 모든 토마토가 다 익었는지 판단후 도대체 무슨 값이 모든 바구니가 다 익었을때 날짜인지 알수 없었다.

2. 또한 아무리 처음에 1인 노드를 큐에 넣고 BFS를 돌린다 하더라도, 1로인해 익은 노드들이 또 익게만드는 노드까지 고려해야 하지 않을까? 

 

이 두 의문을 해결하지 않고는 문제를 풀지 못하였다. 그런데 아주긴 고민 끝에 실마리를 찾았다.

 

1. 바구니가 다 찬 시점 -> 맨 마지막 덜익은 토마토가 익어버리는 시점 -> 맨 마지막까지 남은 토마토가 익는 시점은 그 어떤 다른 토마토가 익은 시점보다 느릴것임. -> 각 토마토 의 익는 날짜를 배열에 저장하여, 가장 큰 날을 구하자.

2. 문제에서 최소비용이라 했으므로, 각 노드의 최초방문시 날짜를 저장하게끔 만들어주면 문제 없음, 또한 큐에 넣을때, 덜익은 토마토만(0인것만) 넣도록 조건을 만들었으므로, 다 익은 토마토가 또 들어갈 일은 없음.

import java.util.Queue;
import java.util.Scanner;

public class Main {


    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int M=s.nextInt();
        int N=s.nextInt();
        int[][] arr=new int[N][M];
        int[] dx={-1,1,0,0};
        //하나 하나 if 조건으로 따져서 칸을 이동시킨뒤 큐에 넣기엔 코드가 너무 복잡
        //그래서 for문으로 해당 노드가 갈수 있는 조건을 필터링해서 큐에 넣기로 했음
        // 내 블로그 2178번 풀이 처럼.
        int[] dy={0,0,1,-1};
        int[][] countarr=new int[N][M];
        //해당 칸에 토마토가 익게만들 가장 '최소의 일수'를 저장.
        //즉, countarr[2][4]=9 이면, 2행 4열의 토마토가 익기까지 최소 9일이 걸린다는 뜻.
        //그러나 출력할때는 이 배열의 '최댓값'을 출력해야됨. 아마 이걸 사람들이 몰라서 정답률이
        //낮은듯.
        //배열의 최댓값을 출력하는 이유는 우선 "모든 토마토가 빠짐없이 다 익어야됨" 이 조건에서 찾을수 있음.
        //맨 마지막으로 남은 토마토가 다 익었을떄 비로소 바구니안 모든 토마토가 다 익은 것임.
        //상식적으로 맨 마지막 토마토가 다 익었을때, 그 칸수에 들어갈 수는 나머지 토마토를 익게만든
        //날짜보다 더 클수밖에 없음. 그래서 배열의 최댓값(맨 마지막 토마토가 익은 날짜)를 출력해 주는 것임.

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                arr[i][j]=s.nextInt();
            }
        }
        Queue<Point> queue=new LinkedList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(arr[i][j]==1){
                    queue.add(new Point(i,j,0));
                }
            }
        }
        while (!queue.isEmpty()){
            Point now= queue.poll();
            int x= now.x;
            int y=now.y;
            int count= now.count;
            countarr[x][y]=count;

            for (int i = 0; i < dx.length; i++) {
                int nexti=x+dx[i];
                int nextj=y+dy[i];
                if(nexti<0||nexti>=N||nextj<0||nextj>=M){
                    continue;
                }
                if(arr[nexti][nextj]!=0){
                    continue;
                }
                queue.add(new Point(nexti,nextj,count+1));
                arr[nexti][nextj]=1;

            }
        }
        int Max=Integer.MIN_VALUE;
        for (int i = 0; i < countarr.length; i++) {
            for (int j = 0; j < countarr[i].length; j++) {
                Max=Max>countarr[i][j]?Max:countarr[i][j];
            }
        }

        if(!checker(arr)){
            System.out.println(-1);
        }
        else{
            System.out.println(Max);
        }

    }
    static boolean checker(int[][] arr){
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                if(arr[i][j]==0){
                    return false;
                }
            }
        }
            return true;
    }
    }
    class Point{
    int x;
    int y;
    int count;

        public Point(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }

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

   공부시간 1시간

순공부시간 30분.

 

오늘 오전에도 외근간다고 오전공부를 거의 못했다..ㅠ