[Java] BOJ 1697 숨바꼭질

문제 

문제 링크 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는 정수이다.
• 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

아이디어

• 최소 시간을 구하는 것이므로 최단 거리를 구할때 쓰는 BFS를 썼다.
• BFS를 써서 Queue에 들어있는 값을 빼내서 해당 값을 기준 좌표로 두고 이동 가능한 좌표가 방문하지 않았고 범위를 넘어가지 않는다면 기준 좌표 시간에 1을 더한 값을 해당 좌표 시간 배열에 저장한다.
• 그리고 방문 처리 후, 그 좌표값을 Queue에 저장한다.
• 만약 Queue에서 꺼낸값이 목적 좌표와 같다면 종료한다.

겪은 시행착오

• 처음에 DP라고 생각하고 풀려고 해봤는데 DP를 푸는 방식인 부분 문제 결과값으로 추론을 할 수가 없다고 판단이 되었다.
• 그래서 어제 풀었던 최단 거리를 구할때는 BFS를 쓰니까 최소 시간도 비슷하지 않을까 해서 BFS로 풀었다
• 그리고 ArrayIndex 에러가 났는데.... 범위를 실수로 잘못지정해서 틀렸었다 ㅜㅜ (실수 조심...!)

BFS를 이런식으로 사용해서 풀 수도 있다는 것을 알게 되어서 좋았다!

코드

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

public class BOJ1697 {

    static int N;
    static int K;
    static int time[];
    static boolean visited[];

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        // 수빈이가 있는 위치
        N = Integer.parseInt(st.nextToken());
        // 동생이 있는 위치
        K = Integer.parseInt(st.nextToken());

        // 걸리는 시간을 저장할 배열
        time = new int[100001];

        // 방문 여부 체크
        visited = new boolean[100001];

        BFS(N, K);

        System.out.println(time[K]);
    }

    public static void BFS(int x, int y){
        Queue<Integer> q = new LinkedList<>();

        q.offer(x);

        // 시작 지점을 방문 처리
        visited[x] = true;

        // 시작지점에서 시작지점까지 걸리는 시간은 0이므로 0으로 초기화
        time[x] = 0;

        // Queue가 빌때까지 반복
        while(!q.isEmpty()){
            int n = q.poll();

            // 현재 위치와 도착 위치가 같다면 반복문 종료
            if(n == y){
                break;
            }

            // 이동한 좌표를 저장할 배열
            int move[] = {n - 1, n + 1, n * 2};

            // 이동한 좌표들 즁
            for(int i : move){
                // 범위를 넘어가면 continue
                if(i < 0 || i > 100000){
                   continue;
                }

                // 방문하지 않은 좌표가 있다면
                if(!visited[i]){
                    // 해당 좌표의 시간을 기준 시간 + 1로 저장하고
                    time[i] = time[n] + 1;
                    // 방문 처리 후
                    visited[i] = true;
                    // Queue에 넣음
                    q.offer(i);
                }
            }
        }
    }
}