[BOJ] C++ 13549 숨바꼭질 3 - 과감하게 동시에 시작시키는 bfs

13549번: 숨바꼭질 3

예제

5 17

res : 2

---

처음에 떠올린 풀이는 순간 이동이 한 번에 한 번만 가능한 줄 알고 +- 한 칸과 순간이동 한 것까지 큐에 넣어서 bfs를 돌렸다. 이렇게 구현하면 주의점이 방문 조건을 체크할 때 이미 방문한 것도 다시 방문해서 최단거리로 체크해야 했다. 이 부분 때문에 틀리는 줄 알고 찾아보니 가중치가 0, 1 밖에 없는 그래프 탐색을 위한 0-1 BFS 알고리즘이 있었는데, 내가 구현한 것과 얼추 비슷해서 맞는 풀이인 줄 알았다. 

 

방문 조건을 아무리 바꾸고 질문 글을 뒤져봐도 내 풀이는 틀린 것 같았고, 한 번에 2 -> 4 -> 8 이런식으로 순간 이동이 가능하다는 걸 깨닫고 다시 풀이를 짜봤다.

 

1. 시작점부터 순간 이동 할 수 있는 모든 칸을 큐에 넣는다.

2. 큐에서 하나 꺼내고, 다시 그 칸부터 순간이동 가능한 모든 칸을 큐에 넣는다. 이 때 주의점은 순간 이동 가능한 칸을 큐에 넣는 함수에 0을 입력으로 넣으면 무한 루프에 빠진다.

 

이렇게 알고리즘을 구성하면 0-1 BFS 같은건 신경 쓰지 않고 그냥 평소에 풀던 BFS와 똑같아서 먼저 방문한 게 무조건 최단 거리이다.

/** BFS 13549 숨바꼭질 3 **/
#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
#define MAX 100002
using namespace std;

int dist[MAX];
int N, K;
queue<int> Q;

void tp(int x)
{
    int temp = x;
    if (x == 0)
        return;
    while (temp < MAX)
    {
        if (dist[temp] == -1)
        {
            dist[temp] = dist[x];
            Q.push(temp);
            if (temp == K)
                return;
        }
        temp *= 2;
    }
}
int bfs()
{
    dist[N] = 0;
    Q.push(N);
    tp(N);
    while (dist[K] == -1)
    {
        int cur = Q.front();
        Q.pop();
        for (int next : {cur + 1, cur - 1})
        {
            if (next < 0 || next >= MAX)
                continue;
            if (dist[next] != -1)
                continue;
            dist[next] = dist[cur] + 1;
            Q.push(next);
            tp(next);
        }
    }
    return dist[K];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> K;
    for (int i = 0; i < MAX; i++)
        dist[i] = -1;
    cout << bfs();
}