문제 링크



문제

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

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

입력

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

출력

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



접근 과정

  1. 처음에는 어떤 수학적 규칙이 있지 않을까 생각해 몇차례의 간단한 연산을 통해 풀리지 않을까 기대했지만… ㅋㅋ 아쉽게도 그러진 않았다. 한가지, N의 위치가 K의 위치보다 크다면 이동할 수 있는 방법이 (-1) 밖에 없으므로 (N - K)의 시간이 걸릴 수 밖에 없다. 우선 해당 부분에 대한 예외처리를 해주었다.
  2. 다음은 DP를 적용해보고자 하였다. N을 시작 위치를 시작으로 다음 위치 까지 가는데 걸리는 최소 시간을 캐시에 기록하고 다른 경로를 통해 위치에 도달하였을 때 캐시에 저장된 시간 보다 오래 걸렸다면 탐색을 중단하는 식이다.
  3. 다만 상향식/하향식 방식으로 구현하지 못하는게 시작 위치가 임의의 N 값 이다. 어떻게 구현할까 고민하다 그래프는 아니지만 너비우선탐색(BFS)과 같이 구현하면 괜찮겠다 싶어, BFS와 DP를 섞은 느낌으로 구현하게 되었다.
  4. 풀이를 마치고 다른 사람들의 풀이를 확인해보니 변형 BFS 문제라고 한다. 대신 본인처럼 별도의 캐시 배열을 두지 않고 queue가 아닌 우선순위 큐(priority_queue)나 덱(deque) 같은 자료구조를 사용하여 BFS 중 *2인 경로를 (+-1) 경로보다 우선하여 탐색하도록 구현하는 방식이었다.


소스 코드

#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

struct dest_t {
    int pos;
    int count;
};

int main() {
    int N, K;
    int shortCache[100010];

    // 임의의 큰 수로 초기화
    memset(shortCache, 0x7F, sizeof(shortCache));
    cin >> N >> K;

    if (N >= K) {
        cout << N - K << endl;
        return 0;
    }

    // BFS 탐색 시작
    int dir[2] = {1, -1};
    queue<dest_t> vertices;
    vertices.push({N, 0});

    while (!vertices.empty()) {
        dest_t dest = vertices.front();
        vertices.pop();

        // 현재 위치로 부터 2씩 곱한 모든 위치로 이동. count는 그대로
        int next = dest.pos * 2;
        while (next <= 100000) {
            if (shortCache[next] <= dest.count) { break; }
            shortCache[next] = dest.count;
            vertices.push({next, dest.count});
        }

        // +1, -1 칸씩 이동. 이동시 시간(count) 증가
        for (int i = 0; i < 2; ++i) {
            next = dest.pos + dir[i];
            if (0 <= next && next <= 100000) {
                if (shortCache[next] > dest.count + 1) {
                    shortCache[next] = dest.count + 1;
                    vertices.push({next, dest.count + 1});
                }
            }
        }
    }

    cout << shortCache[K] << endl;
    return 0;
}