BOJ 1697: 숨바꼭질

백윤재·2021년 9월 18일

BFS boj cpp ps

BOJ

목록 보기

13/28

✔ 문제 링크

BOJ 1697: 숨바꼭질

✔ 문제해결전략

그래프 탐색

1차원에서의 BFS(Breadth First Search)

✔ 해결과정

훈련소에서 인편으로 이 문제 받았을 때 DP인 줄 알았는데 놀랍게도 BFS다.

BFS를 통해 시작점에서 연결된 다른 모든 점까지의 최단거리를 구할 수 있고, 2차원에서의 BFS에서 상하좌우로 뻗어 나갔던 것에 주목해 보자. 그러면 수빈이 위치에서 -1, +1, *2로 뻗어 나가면 되겠다는 생각을 할 수 있다.

그런데 2차원 BFS에서 탐색 범위를 map 안으로 한정했던 것처럼 여기서도 탐색 범위를 정해야 한다. 그러지 않으면 계속 *2 되어서 범위가 끝도 없이 커진다.

생각해 보면 탐색 범위를 100000 정도까지만 하면 된다는 결론에 도달할 수 있다. 2 해서 100000을 넘어가는 경우가 생길 수 있지만 그러면 계속 -1 해야 할 텐데 그럴 바에는 -1 하고 2 하는 것이 낫기 때문이다.

결론: 수빈이 위치에서 -1, +1, *2인 곳의 dist 값을 업데이트해 나가면 된다

✔ 정답 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);

    while (!q.empty()) {
        int cur = q.front();
        q.pop();

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

}

✔ Check Point

이 문제에서는 아무 생각 없이 탐색 범위 100000까지로 잡아도 상관없었지만 문제에서 수빈이가 이동할 수 있는 범위가 100000까지라는 언급은 없었다. 따라서 수빈이가 0 ~ 100000 사이에서만 움직인다고 멋대로 가정을 하고 풀면 안 된다는 것 주의하자.