[백준] 1697번 숨바꼭질(JAVA)

문제

- 수빈이는 점 N(0 <= N <= 100,000)에 위치

- 동생은 점 K(0 <= K <= 100,000)에 위치

- 수빈이는 걷거나(1초 뒤에 X-1 또는 X+1로 이동) 순간이동(1초 뒤에 2*X로 이동) 가능

- 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하기

 

해결방법

최단시간을 찾는 문제이기 때문에 BFS를 활용해야겠다고 생각하였다.

주어진 예제로 보았을 때, 수빈이의 위치(N)는 5, 동생의 위치(K)는 17이다.

각 시간이 흐른 뒤 위치를 표시해보면 다음과 같다. 회색으로 표시된 곳은 이미 방문한 위치이다.

각 위치에서 이동 가능한 X-1, X+1, 2*X의 위치를 표시하고 각 위치에서 뻗어나가는 형태이다. 이미 방문한 위치를 제외하고 계속해서 방문을 표시해보면 4초 뒤, 동생이 위치한 17에 도달하는 것을 확인할 수 있다.

처음에 수빈이와 동생이 있는 위치가 같을 때 처리를 해주지 않아서 틀렸었다... 해당 부분도 체크해서 같다면 0초 걸리는 처리를 해줘야한다.

 

코드

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

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

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int result = 1;
        int count = 1;
        boolean[] check = new boolean[100001];		// 방문 여부를 표시할 배열

        Queue<Integer> queue = new LinkedList<>();

        queue.add(N);
        check[N] = true;

	// 수빈이와 동생의 위치가 같다면 이동할 필요없이 0초가 걸림
        if(N == K){
            System.out.println(0);
            System.exit(0);
        }
		
        // 수빈이가 이동하는 곳의 위치를 큐에 담아서 각 위치에서 다시 뻗어나갈 수 있도록 구성
        go : while(!queue.isEmpty()){
            int repeat = count;
            count = 0;
            for(int i = 0; i<repeat; i++){
                int now = queue.poll();
                int minus1 = now-1;
                int plus1 = now+1;
                int mul2 = 2*now;
				
                // 이동 가능한 구역인지 확인하고, 방문하지 않은 곳인지 확인한 뒤 해당 좌표로 이동
                if(check(minus1) && !check[minus1]){
                    check[minus1] = true;
                    queue.add(minus1);
                    count++;
                }
                if(check(plus1) && !check[plus1]){
                    check[plus1] = true;
                    queue.add(plus1);
                    count++;
                }
                if(check(mul2) && !check[mul2]){
                    check[mul2] = true;
                    queue.add(mul2);
                    count++;
                }
	
    		// 동생이 있는 위치라면 반복문 탈출
                if(minus1 == K || plus1 == K || mul2 == K) {
                    break go;
                }
            }
            // 몇 초가 걸렸는지 기록
            result++;
        }
        System.out.println(result);
    }
	
    // 범위 내의 숫자인지 확인
    public static boolean check(int n){
        return n>=0 && n<=100000;
    }
}