맨처음 문제를 보고 수학문제로 공식을 이용해서 접근할수 있지 않을까 했는데 문제 분류가 bfs였기에 그렇게 접근해 보았다.
만약에 시작우치ㅣ가 도착 위치보다 큰경우에는 뒤로 가는경우밖에 없으므로
n-k를 출력하고
나머지 경우에 bfs를 돌기 시작하게 한다.if(n>k){ System.out.println(n-k); }else{ bfs(n,0); System.out.println(answer); }
현재 위치와 시간을 나타내는 class Node를 만든다.
static class Node{ int pos; int time; public Node(int pos, int time){ this.pos=pos; this.time=time; } }
이동하는 위치에 대한 정보를 queue에다가 담기위해 Node를 자료형으로 가지는 Queue 선언 최초의 값을 넣어준다.
map은 한번 방문한 칸인지 체크하기 위해서 선언했다. map의 key는 위치값, value는 그때의 시간을 저장한다. 그래서 이동하고 난 위치가 map의 key에 있는지 체크하고 key에 없을경우에는 그대로 map.put 해주지만 이미 방문한적이 있는경우 서로의 시간값을 비교하여
map에 저장된 시간보다 현재 시간값이 큰경우 더이상 방문할 필요가 없으므로 저장하지 않는다.if(!map.containsKey(now.pos+1)){ queue.add(new Node(now.pos+1,now.time+1)); map.put(now.pos+1,now.time+1); }else{ if(map.get(now.pos+1)>now.time+1){ queue.add(new Node(now.pos+1,now.time+1)); map.put(now.pos+1,now.time+1); } } if(!map.containsKey(now.pos-1)){ queue.add(new Node(now.pos-1,now.time+1)); map.put(now.pos-1,now.time+1); }else{ if(map.get(now.pos-1)>now.time+1){ queue.add(new Node(now.pos-1,now.time+1)); map.put(now.pos-1,now.time+1); } } if(!map.containsKey(now.pos*2)){ queue.add(new Node(now.pos*2,now.time+1)); map.put(now.pos*2,now.time+1); }else{ if(map.get(now.pos*2)>now.time+1){ queue.add(new Node(now.pos*2,now.time+1)); map.put(now.pos*2,now.time+1); } }
현재위가 0보다 작아지게 되면 바로 종료, k와 같아지게 되거나, k보다 커지게 되면 각각의 조건에 맞게 answer 값을 구한다.
if(now.pos>k){ answer = Math.min(answer, now.time + now.pos-k); continue; } if(now.pos<0){ continue; } if(now.pos==k){ answer = Math.min(answer,now.time); continue; }
import java.util.*;
public class Main {
static int n;
static int k;
static int answer = Integer.MAX_VALUE;
static Map<Integer,Integer> map = new HashMap();
static class Node{
int pos;
int time;
public Node(int pos, int time){
this.pos=pos;
this.time=time;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
k = sc.nextInt();
if(n>k){
System.out.println(n-k);
}else{
bfs(n,0);
System.out.println(answer);
}
}
public static void bfs(int idx, int time){
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(idx,time));
map.put(idx,0);
while(!queue.isEmpty()){
Node now = queue.poll();
//System.out.println(now.pos+" "+now.time);
if(now.pos>k){
answer = Math.min(answer, now.time + now.pos-k);
continue;
}
if(now.pos<0){
continue;
}
if(now.pos==k){
answer = Math.min(answer,now.time);
continue;
}
if(!map.containsKey(now.pos+1)){
queue.add(new Node(now.pos+1,now.time+1));
map.put(now.pos+1,now.time+1);
}else{
if(map.get(now.pos+1)>now.time+1){
queue.add(new Node(now.pos+1,now.time+1));
map.put(now.pos+1,now.time+1);
}
}
if(!map.containsKey(now.pos-1)){
queue.add(new Node(now.pos-1,now.time+1));
map.put(now.pos-1,now.time+1);
}else{
if(map.get(now.pos-1)>now.time+1){
queue.add(new Node(now.pos-1,now.time+1));
map.put(now.pos-1,now.time+1);
}
}
if(!map.containsKey(now.pos*2)){
queue.add(new Node(now.pos*2,now.time+1));
map.put(now.pos*2,now.time+1);
}else{
if(map.get(now.pos*2)>now.time+1){
queue.add(new Node(now.pos*2,now.time+1));
map.put(now.pos*2,now.time+1);
}
}
}
}
}