백준1697_숨바꼭질

문제

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

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

입력

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

출력

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

예제 입력 

5 17

예제 출력 

4

[코드]

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class B1697_HideAndSeek {
 
    
    public static boolean visited[];
    public static int minTime = 100000000;
    public static int max, min;
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int subin = sc.nextInt();
        int sister = sc.nextInt();
        visited = new boolean[1000000];
        
        if(subin>sister) {max = subin; min=sister;}
        else {max = sister; min=subin;}
        
        seekSister(subin, sister, 0);
        System.out.println(minTime);
    }
 
    public static void seekSister(int now, int sister, int time){
        
        Queue<MinTimes> Q = new LinkedList<MinTimes>();
        Q.add(new MinTimes(now,time));
 
        while(!Q.isEmpty()){
            
            MinTimes MT = Q.poll();
            now = MT.now;
            time = MT.time;
            
            if(now == sister){
                minTime = Math.min(minTime, time);
                continue;
            }
            
            visited[now] = true;
            
            if(now+1 <= max+1 && !visited[now+1])
                Q.add(new MinTimes(now+1,time+1));    
            
            if(now-1 >= 0 && !visited[now-1])
                Q.add(new MinTimes(now-1,time+1));    
            
            if(now*2 <= max+1 && !visited[now*2])
                Q.add(new MinTimes(now*2,time+1));
            
        }
    }
}
 
class MinTimes{
    int now;
    int time;
    
    public MinTimes(int now, int time){
        this.now = now;
        this.time = time;
    }
}
 

[알고리즘]

BFS 알고리즘으로 풀었다. 방문했던 정점들은 큐에 집어넣지 않은 채로, 현재 꺼낸 점은 방문상태로 바꿔주었다.