[백준 1697] 숨바꼭질

문제 설명

문제 풀기

수빈이는 동생과 숨바꼭질을 하고 있다.
수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다.
만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

생각 정리

기존 2차원 배열에서는 해당 위치에 대한 '상, 하, 좌, 우' 를 탐색했다면, 이번 문제에서는 일직선에서 앞뒤로 움직인다.
따라서 해당 위치-1, 해당위치+1, 해당위치*2를 탐색한다.

정리된 생각에 대한 논리

//이동할 수 있는 위치는 위치-1, 위치+1, 2*위치
        //수빈이의 현위치로부터 탐색시작
            //이때 첫위치를 방문체크하고 queue에 넣는다. (bfs부른다)
        //queue가 빌때까지
            //queue에서 첫번째 요소를 꺼낸다.
            //이동할 수 있는 위치 탐색하면서 
                //방문하지 않았다면 queue에 넣기
                //방문했다면 그냥 넘겨
                //방문하지 않았다면 이전 위치에서의 거리에 1을 더해준다.
                

*해당 위치는 바뀌기 때문에 탐색할 위치를 static으로 고정해서 선언하지 않는다.

완성

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

public class BOJ1697 {

    static int[] position = new int[200000];
    static boolean[] visited = new boolean[200000];
    static int N, K, cnt = 0;
    static int[] dis = new int[200000];
    static Queue<Integer> queue = new LinkedList<>();

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

        N = Integer.parseInt(st.nextToken()); //수빈이의 현위치
        K = Integer.parseInt(st.nextToken()); //동생의 현위치

        if(N == K)
            System.out.println(0);
        else{
            visited[N] = true;
            queue.add(N);
            bfs(N);
        }
    }

    static void bfs(int N) {
        boolean flag = false;

        while(!queue.isEmpty()) {
            int p = queue.poll();
            int[] d = {-1, 1, p};
            
            for(int i=0; i<3; i++) {
                int next = p + d[i];
                
                if(next < 0 || next > 100000) continue;
                else if(visited[next] == true) continue;
                else{
                    visited[next] = true;
                    queue.add(next);
                    dis[next] = dis[p] + 1;
                    
                    if(next == K) {
                        flag = true;
                        cnt = dis[next];
                    }
                    
                }
            }

            if(flag){

                System.out.println(cnt);
                break;
            }

        }

    }
}