문제

풀이

• dfs는 느리니까 bfs로 해주기
• 방문 처리는 Set으로 했다.
• 음수, 20만 이상 넘어가는 것 조건 처리
• 정답 찾으면 즉시 종료

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st=new StringTokenizer(br.readLine());
        int n=Integer.parseInt(st.nextToken());
        int k=Integer.parseInt(st.nextToken());
        if(n==k) {
            System.out.println(0);
            return;
        }

        Queue<Move> q=new LinkedList<>();
        q.add(new Move(n,0));
        int ans=Integer.MAX_VALUE;
        HashSet<Integer> set=new HashSet<>();
        set.add(n);
        boolean flag=false;
        int[] d=new int[]{1,-1,2};
        while(!q.isEmpty()){
            Move now=q.poll();
            for(int i=0;i<3;i++){
                int next;
                if(i==2)next=now.point*d[i];
                else next=now.point+d[i];

                if(next==k){
                    ans= now.time+1;
                    flag=true;
                    break;
                }
                if(next<-1||next>200000)continue;
                if(!set.contains(next)){
                    set.add(next);
                    q.add(new Move(next, now.time+1));
                }
            }
            if(flag)break;
        }
        System.out.println(ans);
    }

    static class Move{
        int point,time;

        public Move(int point, int time) {
            this.point = point;
            this.time = time;
        }
    }
}

#bfs