1. 문제설명

출발점은 N(0<=N<=100,000), 도착지는 K(0<=N<=100,000)
특징 위치가 X일 때,
- X-1, X+1의 위치로 이동할 수 있고, 이 때의 가중치는 1
- 2*X의 위치로 이동할 수 있고, 이 때의 가중치는 0
최단 거리 계산

2. 알고리즘 설계

BFS 문제로 최단 경로를 구한다. 일줄 알았지만 아니다..
- BFS는 가중치의 우선순위 없이 하나의 가중치라는 전제로 최단거리를 찾기 때문이다.
0-1 BFS 문제로 Deque 혹은 Dijkstra로 구현 가능하다.
- Deque는 두 종류의 가중치만 구현 가능하다.

3. 로직

처음 접근은 BFS였다.
- 당연히 ‘틀렸습니다’를 보게 되었다.

Deque

weight가 0이면 앞에, 아니라면 뒤에 삽입

auto cur = dq.front();
dq.pop_front();
  
if(weight = 0 && !visited)
  dq.push_front(next)
else
  dq.push_back(next)

priority_queue (min heap)

순위 보장
greater<>를 사용하려면 {weight, node} 순으로 삽입해야 함.

typedef pair<int.int> pii;
priority_queue<pii, vector<pii>, greater<pii>> pq;

pii cur = pq.top();
pq.pop();

if(!visited)
  pq.push(next)

4. 전체 코드

본인은 Deque 기반으로 Solve

#include <iostream>
#include <deque>
using namespace std;
 
#define SZ 100000+1
 
int N, K;
int visited[SZ];
 
int bfs() {
    deque<int> dq;
    dq.push_front(N);
    visited[N] = 1;

    while (!dq.empty()) {
        int x = dq.front();
        dq.pop_front();

        if (x == K) return visited[K] - 1;

        int nx = x * 2;
        if (nx < SZ && !visited[nx]) {
            dq.push_front(nx);
            visited[nx] = visited[x];
        }

        nx = x + 1;
        if (nx < SZ && !visited[nx]) {
            dq.push_back(nx);
            visited[nx] = visited[x] + 1;
        }

        nx = x - 1;
        if (nx >= 0 && !visited[nx]) {
            dq.push_back(nx);
            visited[nx] = visited[x] + 1;
        }
    }
}
 
int main() {
    cin >> N >> K;
    cout << bfs();
    return 0;
}

5. 소감

BFS 문제를 많이 풀어보기도 했고,
- 2*X에 대해 가중치를 0을 부여하면 되겠구나 생각
만약 X+1, 2*X 모두 큐에 들어가 있다면,
- 먼저 큐에 들어간 게 처리되어 정답이 처리될 수 있다.
최단 거리는 2*X를 통해 가는 것이지만,
- X+1로도 갈 수 있다면, 이게 최단거리가 되어 종료되는 것이다.
숨바꼭질 1과 문제가 너무 유사해서 쉽겠구나 생각했는데…
- 아직 갈길이 멀구나..

BOJ 13549. 숨바꼭질 3

1. 문제설명

2. 알고리즘 설계

3. 로직

4. 전체 코드

5. 소감