[Algorithm] 백준 1697번_숨바꼭질(Java)

🔗 1946번 신입 사원

https://www.acmicpc.net/problem/1697

 

 

 

문제

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

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

 

입력

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

 

출력

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

 

💡 접근 방법 및 풀이

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.라는 것을 보고 힌트를 얻었다. 

BFS를 사용해서 풀어보자

 

💻 코드

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


public class Main {
    public static int N;
    public static int K;
    public static int[] dx = {-1, 1, 2};
    public static int[] count;
    public 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());
        count = new int[100001];

        count[N] = 1;
        queue.add(N);

        if (N == K) {
            System.out.println(0);
        } else {
            bfs();
        }

    }

    public static void bfs () {
        while (!queue.isEmpty()) {
            int now = queue.poll();

            for(int i = 0; i < 3; i++) {
                int next;
                if(i == 2) {
                    next = now * dx[i];
                } else {
                    next = now + dx[i];
                }
                if(next == K) {
                    System.out.println(count[now]);
                    return;
                }
                if(next >= 0 && next <= 100000 && count[next] == 0) {
                    queue.add(next);
                    count[next] = count[now] + 1;
                }
            }
        }
    }
}