백준 13913 숨바꼭질 4 (C++)

13913번: 숨바꼭질 4

bfs를 이용한 문제이다. 이전에 풀었던 숨바꼭질과 연계되는 문제이다. bfs를 이용해 최단 시간을 찾는 것은 동일하다. 다른 점은 방문했던 곳을 체크할 때 true, false가 아닌 이전 위치를 저장해주었다. bfs를 끝낸 후 도착 지점부터 시작 지점까지 거슬러 올라가면서 위치를 저장해 출력해주었다. 어렵지 않게 풀 수 있었던 문제였다. 다만 배열 범위를 잘못 작성해 시간 낭비를 좀 했었다. 이부분을 주의하자.

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

int N, K, mint;
int check[100001];
int result[100001];
int dx[2] = { 1,-1 };

void findResult() {
    int nc = K;
    for (int i = mint; i >= 0; i--) {
        result[i] = nc;
        nc = check[nc];
    }
}

void bfs() {
    queue<pair<int, int>> q;

    check[N] = N;
    q.push({ N,0 });

    while (!q.empty()) {
        int x = q.front().first;
        int time = q.front().second;

        q.pop();

        if (x == K) {
            mint = time;
            break;
        }

        for (int i = -1; i < 2; i++) {
            int nx = i == -1 ? x * 2 : x + dx[i];
            int nt = time + 1;

            if (nx < 0 || nx > 100000) continue;
            if (check[nx] != -1) continue;
            
            check[nx] = x;
            q.push({ nx,nt });
        }
    }
}

void solution() {
    memset(check, -1, sizeof(check));

    bfs();
    findResult();

    cout << mint << "\n";
    for (int i = 0; i <= mint; i++) {
        cout << result[i] << " ";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> K;

    solution();

    return 0;
}