BOJ 13913 : 숨바꼭질 4

풀이 요약

BFS, 대표값 찾기

풀이 상세

1. 문제에서 중요한 키 포인트는 2가지이다.
2. DFS 보다 BFS 가 빠르다는 점을 파악해야 한다. 문제는 가장 빠른 시간을 찾는 것을 원하기 때문에 최단 경로를 구하는 BFS 가 적절하다.
3. 거쳐가는 위치를 어떻게 구할건지를 고민해봐야 한다. 단순히 리스트를 복사하는 식으로 푸는 경우는 에러가 나더라. 찾은 방법은 이전 값을 저장하는 배열을 만들어 BFS 종료 후에 이전 값을 탐색해 가며 시작값까지 도달하는 방식을 사용하였다.

배운 점

• 나의 경우 백터를 주로 사용하며, 이를 문제에 맞게 초기화하여 사용하는 편인데 초기화 시에는 O(N) 만큼의 시간이 필요하다. (시간 초과 주의)
• 확실히 백터 보다는 배열이 같은 사이즈 대비 메모리를 덜 차지한다.

#include <iostream>
#include <queue>

using namespace std;
int N, M, v[100001], p[100001];

void input() {
    cin >> N >> M;
}

void bfs() {
    queue<int> q, q.push(N);
    v[N] = 1, p[N] = N;
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        if (curr == M) break;
        for (int n: {curr + 1, curr - 1, curr * 2}) {
            if (n > 100000 || n < 0) continue;
            if (v[n]) continue;
            v[n] = v[curr] + 1;
            p[n] = curr;
            q.push(n);
        }
    }
}

void output() {
    cout << v[M] - 1 << "\n";
    vector<int> ans;
    while (true) {
        ans.push_back(M);
        if (M == p[M]) break;
        M = p[M];
    }
    for (int i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i] << " ";
    };
}

int main() {
    input();
    bfs();
    output();
}