Notice
Recent Posts
문제 풀이 및 개발 공간
[백준] 12851번 숨바꼭질 2 (gold 4 본문
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();
}
}
'백준공부 > java' 카테고리의 다른 글
[백준] 1238번 파티 (gold 3 (0) | 2024.03.11 |
---|---|
[백준] 5635번 생일 (silver 5 (0) | 2024.03.10 |
[백준] 1043번 거짓말 (gold 4 (0) | 2024.03.09 |
[백준] 20951번 유아와 곰두리차 (gold 5 (0) | 2024.03.08 |
[백준] 20950번 미술가 미미 (silver 2 (0) | 2024.03.08 |