BOJ 13913 : 숨박꼭질 4

문제

---

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

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

 

입력

---

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

 

 

출력

---

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

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

 

 

틀리기 쉬운 점

---

 

1. 배열의 크기

수빈이와 동생의 이동범위는 0 ~ 100,000 까지이다.
하지만 100,000 위치에서 순간이동하는 것을 고려하여 MAX=200'000 로 하자.

 

2. BFS 탐색이 배열의 범위를 초과하지 않아야 한다.

 

 

코드

---

#include <iostream>
#include <queue>

using namespace std;
#define MAX 200000

bool check[MAX+5];
int d[MAX+5];        //거리
int pre[MAX+5];        //이전 위치
// 100,000 위치에서 순간이동할때의 최댓값은 200,000이다.

//이동경로를 출력해주는 재귀함수
void print(int n, int m) {
    if (n != m)
        print(n, pre[m]);

    cout << m << ' ';
}

int main() {

    int n, k;        //수빈,동생
    cin >> n >> k;

    queue <int> q;
    q.push(n);
    check[n] = true;
    d[n] = 0;

    while (!q.empty()) {
        int x = q.front();
        q.pop();
        if (x - 1 >= 0) {
            if (!check[x - 1]) {
                check[x - 1] = true;
                q.push(x - 1);
                d[x - 1] = d[x] + 1;
                pre[x - 1] = x;
            }
        }
        if (x + 1 < MAX) {
            if (!check[x + 1]) {
                check[x + 1] = true;
                q.push(x + 1);
                d[x + 1] = d[x] + 1;
                pre[x + 1] = x;
            }
        }
        if (x * 2 < MAX){
            if (!check[x * 2]) {
                check[x * 2] = true;
                q.push(x * 2);
                d[x * 2] = d[x] + 1;
                pre[x * 2] = x;
            }
        }
    }
    cout << d[k] << '\n';
    print(n, k);
    cout << '\n';

    return 0;
}

코드

---

import java.util.*;

public class Main {

    public static final int MAX = 200000;

    static void print(int[] pre, int n, int k) {
        if(n != k)
            print(pre, n, pre[k]);
        System.out.print(k + " ");
    }


    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] pre = new int[MAX+5];
        boolean[] check = new boolean[MAX+5];
        int[] d = new int[MAX+5];

        check[n] = true;
        d[n] = 0;
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(n);
        while(!q.isEmpty()) {
            int x = q.remove();
            if(x-1 >=0) {
                if(!check[x-1]) {
                    q.add(x-1);
                    check[x-1]=true;
                    d[x-1]=d[x]+1;
                    pre[x-1]=x;
                    }
            }
            if(x+1 < MAX) {
                if(!check[x+1]) {
                    q.add(x+1);
                    check[x+1]=true;
                    d[x+1]=d[x]+1;
                    pre[x+1]=x;
                    }
            }
            if(x*2 < MAX) {
                if(!check[x*2]) {
                    q.add(x*2);
                    check[x*2]=true;
                    d[x*2]=d[x]+1;
                    pre[x*2]=x;
                    }
            }            
        }    
        System.out.println(d[k]);
        print(pre, n, k);
        System.out.println();

    }
}