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

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

문제

---

0 1 2 3 ... 100000 으로 이루어진 일자형 길에 x+1, x-1 2*x로 움직일 수 있다고 했을 때 목적까지 가는 최단 경로를 구하는 문제이다.

아이디어

---

단순 BFS문제이다. 하지만 visit으로 최단 경로보다 이후에 간 인덱스는 방문처리하여 다시 방문하지 않도록 한다.

 

여기까지는 스스로 짰지만 이후에도 메모리 초과가 걸렸다.

왜냐하면 최단 경로를 vector를 사용하여 리스트처럼 저장을했는데

이는 상당히 많은 배열을 큐에 저장하기 때문이다.

단순하게 생각해보면 벡터의 크기가 1에서 100000까지인데 방문한 인덱스를 제외하면 최대 1에서 33333까지 3개씩 저장해 나갈 것이다.

(1,2,2,2,3,3,3,4,4,4....) 그러면 1~33333까지의 총합을 구해서x 3하고  x4bytes해주면 적어도 2GB가 된다.

여기에 더해 vector의 capacity 할당하는 방식은 조금 다르기 때문에 이보다 더 많은 메모리를 차지하게 될 것이다.

 

이를 해결하기 위한 방식으로 visit의 인덱스에 부모 노드에 대한 인덱스를 담는 것이다.

만약 1→2 →4가 4로가기 위한 최단경로로 채택되었을 때, 1 →2 →3 →4는 visit 정보때문에 최단이 아니란 걸 알아서 두 번이상의 방문할 일이 없다.

따라서 visit배열에 부모 노드의 인덱스를 저장해주고 목적지 인덱스에 도착하였을 때 역순으로 부모 노드를 찾아 출력한다.

Code

---

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

void init() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);
}

const int MAX = 100000;
int visit[MAX + 1];

void bfs(int N, int K) {
    queue<pair<int, int>> q;
    fill(visit, visit + MAX + 1, -1);
    q.push({N, 0});
    visit[N] = N;

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

        if (current == K) {
            cout << time << '\n';
            // 역추적
            vector<int> path;
            for (int i = K; i != N; i = visit[i]) path.push_back(i);
            path.push_back(N);

            for (int i = path.size() - 1; i >= 0; i--) cout << path[i] << " ";
            cout << '\n';
            return;
        }

        vector<int> next_positions = {current - 1, current + 1, current * 2};
        for (int next : next_positions) {
            if (next >= 0 && next <= MAX && visit[next] == -1) {
                q.push({next, time + 1});
                visit[next] = current;
            }
        }
    }
}

int main() {
    init();
    int N, K;
    cin >> N >> K;
    bfs(N, K);
    return 0;
}