[백준 - 1697] 숨바꼭질 - java

[백준 - 1697] 숨바꼭질 - java

---

문제 설명

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

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

 

입력

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

 

출력

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

 

 

풀이

BFS를 이용하는 문제다.

지금까지 풀었던 bfs는 2차원 배열을 순회하는 문제들이였는데

이번에는 그냥 1차원 배열을 bfs로 푸는 문제였다.

 

일반적으로 bfs 문제에서 많이 나오는 상하좌우 이동 문제가 아닌 +1, -1, *2 와 같이 3가지 이동만 있었다.

방문 여부를 체크해주는 visited 1차원 배열과 걸리는 시간을 저장할 time 1차원 배열을 이용했다.

 

그리고 만약 수빈이가 동생의 위치보다 큰 위치에 있다면 -1 move만을 이용하여 만나는 방법밖에 없기 때문에

bfs 돌리기전에 체크하여 크다면 n-k를 return해줬다.

 

코드

package baekJoon.BFS;
 
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class B_1697 {
 
 
    static boolean[] visited = new boolean[100001];
    static int[] time = new int[100001];
    static int[] move = { 1, -1, 2 };
 
    private static void solution () {
        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
        int k = sc.nextInt();
 
        if(n >= k)
            System.out.println(n-k);
        else
            bfs(n, k);
    }
 
    public static void bfs (int n, int k) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(n);
        visited[n] = true;
        time[n] = 0;
 
        while(!queue.isEmpty()) {
            int num = queue.poll();
 
            for(int i=0; i<3; i++) {
                int next;
                if(i == 2) {
                    next = num * move[i];
                } else {
                    next = num + move[i];
                }
 
                if(next <= 100000 && -1 < next && !visited[next]) {
                    queue.add(next);
                    visited[next] = true;
                    time[next] = time[num] + 1;
                }
            }
        }
        System.out.println(time[k]);
    }
 
    public static void main(String[] args) {
        solution();
    }
}