[1697] 숨바꼭질(BFS)

문제

---

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

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

 

입력

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

출력 

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

 

예시

5 17
//4

 

Key Point

---

• 레벨 순회로 이동 거리 체크

 

풀이

---

1. 큐에 시작 위치 저장
2. 이동 거리 한 번씩 적용하면서 현재 위치 확인 및 방문 체크
3. 방문한적 없으면 방문 표시, 현재 위치 큐에 저장
4. 레벨 순회 종료
5. 다음 레벨 순회 반복

public class HideSeek {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        System.out.println(BFS(n,k));
    }

    public static int BFS(int n, int k){
        int [] visited = new int[100001];	//탐색할 범위 초기화
        int [] move = {-1,1,2};		//이동 범위
        Queue<Integer> q = new LinkedList();
        visited[n] = 1;		//시작 위치 방문 처리
        q.offer(n);		//큐에 시작 위치 저장
        int level=0;		//순회할 레벨(=move 한번 도는 싸이클) 초기화
        while(!q.isEmpty()){
            int len = q.size();		//큐 사이즈 만큼 순회
            for(int i=0; i<len; i++){
                int x = q.poll();		//큐에서 이동 범위 계산할 위치 저장
                for (int j = 0; j < 3; j++) {
                    int nx;
                    if(n==k) return 0;		//엣지 케이스 처리
                    //이동 범위 적용
                    if(move[j]==2){
                        nx = x*move[j];
                    }
                    else{
                        nx = x+move[j];
                    }
                    //next actions
                    if (nx == k) {		//지정 범위 도착 시 종료
                        return level+1;
                    }
                    if(nx>0 && nx<=100000 && visited[nx]==0){
                        visited[nx] =1;		//방문 처리
                        q.offer(nx);		//큐에 현재 위치 저장
                    }
                }
            }level++;		//레벨 순회 끝날 때 마다 ++
        }return 0;
    }
}