[C++] BOJ 13549 / BFS (숨바꼭질 3)

문제 분석

 

https://www.acmicpc.net/problem/13549

 

숨바꼭질1 (BOJ 1697) 의 변형 문제이다.

해당 문제와 다른 점은 2*X 이동을 하는 순간이동에 걸리는 시간이 "0초" 라는 점이다.

 

해결 방법

단순히 2*X 이동 할 때는 dist를 이전dist에서 1을 더해주지 않으면 된다. (1초가 아닌 0초기 때문)

 

코드

#include <iostream>
#include <queue>
#include <utility>

int dist[200001];

using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    queue<int> q;
    int n,k;
    cin >> n >> k;
    q.push(n);
    dist[n] = 1;
    while(!q.empty()) {
        int flag=0;
        int cur = q.front();
        q.pop();
        if(cur == k) {
            break;
        }
        for(int e : {cur*2, cur-1, cur+1}){
            flag++;
            if(e < 0 || e > 200000) continue;
            if(dist[e] != 0) continue;
            q.push(e);
            if(flag == 1) {
                dist[e] = dist[cur];
            } else {
                dist[e] = dist[cur] + 1;
            }
        }
    }
    cout << dist[k] - 1;
}

 

풀이 복습

코드를 짜며 따져주지 못했던 부분 때문에 첫 시도는 틀렸습니다가 나왔다.

반례는 for(int e : {cur-1,cur+1,cur*2}) 이 부분 때문에 발생했는데, cur+1이 cur*2보다 먼저 e 에 들어가므로, +1 한 것과 *2 한 것이 같을 때 문제가 된다.

자세히 설명하자면, 예를 들어 입력 값이 1 3 이면, 정답은 1 이지만, 출력은 2가 나오게 된다. 왜냐하면 cur+1이 먼저 들어가서 dist 값을 바꿔놓기 때문에 cur*2를 계산하지 못하기 때문이다.

이 문제는 for range의 순서를 위 코드처럼 바꿔서 해결하였다. *2 한 것은 0초 이므로, 항상 +1 하는 것 보다 dist에 작은 값이 들어갈 수 밖에 없다.