[백준 1697번] 숨바꼭질

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

---

정답

어렵게 생각하지말고 숫자하나하나가 노드이고 각 노드한 방향 간선이 3개씩 있다고 생각하고 너비탐색으로 풀면 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Queue;

public class Main {
    static class Graph{
        int [] position;
        int ans;
        public Graph(int size, int ans) {
            position = new int[size+1];
            this.ans = ans;
        }
        public void BFS(int n,int k) {
            Queue<Integer> que = new LinkedList<Integer>();
            boolean [] visited = new boolean[this.position.length];

            que.add(n);
            visited[n]=true;
            position[n] = 0;

            while(!que.isEmpty()) {
                int now = que.poll();
                visited[now]=true;

                for(int i=0;i<3;i++) {
                    int nextpos=0;
                    if(i==0) {
                        nextpos = now+1;
                    }else if(i==1) {
                        nextpos = now-1;
                    }else if(i==2) {
                        nextpos = now*2;
                    }
                    if(nextpos >=0 && nextpos<position.length && visited[nextpos] == false ) {
                        position[nextpos] = position[now]+1;
                        visited[nextpos] = true;
                        que.add(nextpos);
                    }
                }
                if(position[k]!=0 || now == k) {
                    System.out.println(position[k]);
                    break;
                }
            }
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String [] NK = br.readLine().split(" ");

        int n = Integer.parseInt(NK[0]);
        int k = Integer.parseInt(NK[1]);
        Graph g = new Graph(100000,k);


        //너비탐색
        g.BFS(n,k);

        br.close();
        bw.flush();
        bw.close();
    }
}