BOJ 13549: 숨바꼭질 3

✔ 문제 링크

---

BOJ 13549: 숨바꼭질 3

---

✔ 문제해결전략

• 그래프 탐색
• 1차원에서의 BFS(Breadth First Search)

---

✔ 해결과정

• BOJ 1697: 숨바꼭질에서 *2는 0초 만에 가능한 것으로 바뀌었다.
• BFS를 할 때 시작점이 여러 곳인 경우 시작점을 모두 queue에 넣고 시작하면 된다는 것을 떠올려보자.
• 그러면 현재 점에서 BFS를 하기 전에 현재 점 *2인 곳은 거리를 현재 점과 같도록 하고 queue에 넣은 다음에 BFS를 돌리면 된다.

---

✔ 정답 Code

#include <bits/stdc++.h>
using namespace std;

int dist[100002];

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

    int n, k;
    queue < int > q;
    cin >> n >> k;

    fill(dist, dist + 100001, -1);
    dist[n] = 0;
    q.push(n);
    if (2 * n <= 100000) { // new
        dist[2 * n] = 0;
        q.push(2 * n);
    }

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        int target = 2 * cur;
        if (!(target < 0 || target > 100000) && !(dist[target] != -1)) {
            dist[target] = dist[cur];
            q.push(target);
        }

        for (int new_: {
                cur - 1,
                cur + 1
            }) {
            if (new_ < 0 || new_ > 100000) continue;
            if (dist[new_] != -1) continue;
            dist[new_] = dist[cur] + 1;
            q.push(new_);
        }
    }
    cout << dist[k];

}

---

✔ Comment

알고리즘 분류를 보니 0-1 BFS라는 게 있었다. 그냥 아무 생각 없이 풀었는데 이것도 따로 분류가 있구나.