[백준 알고리즘] 1697번 자바(Java) 숨바꼭질 BFS

조건

문제

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

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

 

입력

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

출력

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

 

풀이

시간복잡도 면에서 주어진 수는 10만이다. 따라서 이중for문을 쓰면 안되고
O(nlogn)으로 풀수있는 방법을 생각해야한다. 

수빈이가 이동할수있는곳을 방문체크하듯이 진행하면 각 칸마다의 최소 이동시간을 알 수 있게된다.

따라서 너비우선탐색(BFS)를 사용했다.

과정은 다음과 같다. 수빈 위치가 5, 동생이 17에 있다고 가정하고 그림을 보면 될것같다.

5가 수빈이의 위치고 queue에는 5가 들어간다

5에서 (5-1),(5+1),(5*2) 이동한 4,6,10이 큐에 들어간다

4, 6, 10에서 이동가능한 칸들을 큐에 넣는다

3,8,7,14,9,11,20에서 가능한 수를 큐에 넣었다.(참고로 22이상의 수는 그림 설명상 넣지 않았다. - 실제로는 큐에 들어감!)

16을 통해서 17도달

이런 과정을 통해 수진의 위치 5에서 동생의 위치 17까지 도달하는 빠른시간은 4 이다.

그림이 이해가 안가거나 BFS문제가 어렵게 느껴진다면 아래 링크글에 있는 문제와 그림(큐 그림 위주로)
을 봐주면 될것같다.

https://developerjisu.tistory.com/3

 

예제 입력 예시

5 17

예제 출력

4

 

소스코드

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

//1697번

public class Main {
    static boolean[] visited;    //방문체크
    static int[] map;      //숨바꼭질 맵
    static int K;     //동생의 위치

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        map = new int[100001];
        visited = new boolean[100001];
        int N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        //동생이 수빈이보다 오른쪽에 있는 경우
        if(N<K){
            bfs(N);
            System.out.println(map[K]);
        }
        //동생이 수빈이보다 왼쪽에 있는 경우
        else System.out.println(N-K);
    }

    static void bfs(int n){
        Queue<Integer>queue = new LinkedList<>();
        queue.add(n);
        map[n] = 0;
        visited[n] = true;
        while(!queue.isEmpty()){
            int start = queue.poll();
            if(start>0&&!visited[start-1]){    
                queue.add(start-1);
                visited[start-1] = true;
                map[start-1] = map[start]+1;
            }
            if(start<100000&&!visited[start+1]){
                queue.add(start+1);
                visited[start+1] = true;
                map[start+1] = map[start]+1;
            }
            if(start<50001&&!visited[start*2]){
                queue.add(start*2);
                visited[start*2] = true;
                map[start*2] = map[start]+1;
            }
        }
    }
}

 

 

 

 

문제 출처

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

1697번: 숨바꼭질