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

문제

백준 13913 숨바꼭질 4 C++

13913번: 숨바꼭질 4

풀이

숨바꼭질에서 경로를 저장하는 배열 vector<int>만 추가해주면 될 줄 알았더니 메모리 초과가 떴습니다.

곰곰히 생각해보니 방문하는 모든 지점을 각각의 queue에 저장하는 것이 문제였습니다.

따라서 가장 처음 해당 지점을 방문할 때, 어디서 방문했는지 저장하는 배열을 선언하여 최단 경로만을 저장하는 방식으로 해결하였습니다.

소스 코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define max 1000001
 
int N, K;
int parent[max];
bool visited[max];
 
// 현재 위치와 걸린 시간
struct node
{
    int cur;
    int time;
};
 
void bfs(int start) {
    queue<node> q;
    q.push({ start, 0 });
    while (!q.empty()) {
        int cur = q.front().cur;
        int time = q.front().time;
        q.pop();
        // 목적지 도착 하면 종료
        if (cur == K) {
            cout << time << endl;
            return;
        }
        // 해당 지점을 처음 방문하는 경우 부모 설정 및 방문 처리
        if (cur * 2 < max) {
            if (!visited[cur * 2]) {
                visited[cur * 2] = true;
                q.push({ cur * 2, time + 1 });
                parent[cur * 2] = cur;
            }
        }
        if (cur + 1 < max) {
            if (!visited[cur + 1]) {
                visited[cur + 1] = true;
                q.push({ cur + 1, time + 1 });
                parent[cur + 1] = cur;
            }
        }
        if (cur - 1 >= 0) {
            if (!visited[cur - 1]) {
                visited[cur - 1] = true;
                q.push({ cur - 1, time + 1 });
                parent[cur - 1] = cur;
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> N >> K;
    bfs(N);
    vector<int> v;
    while (1) {
        // 끝 -> 시작으로 경로 찾으며 올라가기
        v.push_back(K);
        if (K == N) {
            break;
        }
        K = parent[K];
    }
    // 앞에서부터(시작점부터) 출력
    for (int i = v.size() - 1; i >= 0; i--) {
        cout << v[i] << ' ';
    }
    return 0;
}