문제 풀이 및 개발 공간

[백준] 12851번 숨바꼭질 2 (gold 4 본문

백준공부/java

[백준] 12851번 숨바꼭질 2 (gold 4

gomduri43 2024. 3. 10. 18:24

import java.util.*;
import java.io.*;

class Point{
    int x;
    int t;
    public Point(int x, int t){
        this.x=x;
        this.t=t;
    }
}
public class Main{
    public static void main(String[] args ) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st=new StringTokenizer(br.readLine());

        int n=Integer.valueOf(st.nextToken());
        int k=Integer.valueOf(st.nextToken());

        int min=Math.abs(k-n);
        int num=0;

        Queue<Point> que=new LinkedList<>();
        int end= n>k ? 2*n+1 : 2*k+1;

        //좌표 마다 그 위치에 갈때의 최솟값저장.
        //차피 해당수에서 k까지 도달하는 최소거리는 똑같을 수 밖에 없다.
        //같은 수에서 출발 케이스이므로. 따라서 이 최소거리를 넘어가는 케이스들은 무시하면서 진행

        int[] visit=new int[end];
        Arrays.fill(visit, Integer.MAX_VALUE);
        visit[n]=0;

        que.offer(new Point(n,0));
        while(!que.isEmpty()){
            Point temp=que.poll();
            if(min<temp.t){
                continue;
            }
            if(temp.x==k && temp.t<=min){
                if(temp.t<min){
                    min=temp.t;
                    num=1;
                }
                else{
                    num++;
                }
                continue;
            }

            if(temp.x==0){
                que.offer(new Point(temp.x+1, temp.t+1));
                continue;
            }
            //k를 넘어가면 무조건 k에 가려면 -1-1-1-1-1식으로 가야됨.
            //따라서 이때의 3케이스 분기를 줄이기 위해 한번에 도착점으로
            else if(temp.x>=k){
                que.offer(new Point(k, temp.t+temp.x-k));
                continue;
            }

            if(temp.x+1<=end && visit[temp.x+1]>=temp.t+1){
                visit[temp.x+1]=temp.t+1;
                que.offer(new Point(temp.x+1, temp.t+1));
            }
            if(temp.x-1<=end && visit[temp.x-1]>=temp.t+1){
                visit[temp.x-1]=temp.t+1;
                que.offer(new Point((temp.x-1) , temp.t+1));
            }
            if(temp.x*2<=end && visit[temp.x*2]>=temp.t+1){
                visit[temp.x*2]=temp.t+1;
                que.offer(new Point((temp.x*2) , temp.t+1));
            }

        }
        bw.write(min+"\n");
        bw.write(num+"");
        bw.flush();

    }
}