[백준][13549번: 숨바꼭질 3]

🎈문제

문제링크

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

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

🎈입력

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

🎈출력

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

🎈접근방법

bfs을 통해서 조건을 따져서 큐에 넣는다.
조건에서 연산순서가 중요하다. 그래서 를 제일 먼저 놓고 계산한다.
ex) 1에서 2로 가고자 할 때 최소시간은 +1 하는 것보다 2를 하는 것이 더 효율적이기 때문에

🎈코드

package BaekJoon.P13549;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * https://www.acmicpc.net/problem/13549
 * [13549번: 숨바꼭질 3]-Gold5
 */

public class Main {
    static int N,K;
    static boolean[] visited;
    static int min = Integer.MAX_VALUE;
    static int M = 100000;
    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());

        visited = new boolean[M*2];
        if(N==K){
            System.out.println(0);
        }else {
            bfs(N);
            System.out.println(min);
        }
    }
    static void bfs(int start){
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(start,0));
        visited[start] = true;
        while(!queue.isEmpty()){
            Node now = queue.poll();

            if(now.num==K){
                min = Math.min(min,now.time);
            }
            if(now.num*2 <= M && !visited[now.num*2]){
                visited[now.num*2] =true;
                queue.add(new Node(now.num*2, now.time));
            }
            if(now.num-1 >= 0 && !visited[now.num-1]){
                visited[now.num-1] =true;
                queue.add(new Node(now.num-1, now.time+1));
            }
            if(now.num+1 <= M && !visited[now.num+1]){
                visited[now.num+1] =true;
                queue.add(new Node(now.num+1, now.time+1));
            }
        }

    }
    static class Node{
        int num;
        int time;

        public Node(int num, int time) {
            this.num = num;
            this.time = time;
        }
    }

}