백준 13913번: 숨바꼭질 4

백준 13913: 숨바꼭질 4

13913번: 숨바꼭질 4

 

예전에 풀었던 숨바꼭질 시리즈인데 오랜만에 풀어서 그런지 시간초과로 한번에 풀지를 못했다. 결국 예전 코드를 참조해서 다시 기억을 되살려서 풀어냈다. DFS를 사용하면 시간초과가 나고 BFS를 사용하는편이 정신건강에 이롭다. 코드 풀이는 간단하다. 앞으로 한칸, 뒤로 한칸, 앞으로 두배 이동 이렇게 세개의 경우만 큐에 푸쉬를하고 가장 먼저 탐색되는 경우가 최소 걸리는 시간이다. 이때 해당 경로로올때 바로 이전 원소를 저장하는 배열을 가지는 배열 변수가 필요하고, 최소 거리를 찾았을 때 이전 노드로 되돌아가면서 벡터에 push하는 방법으로 최소 이동 경로를 파악할 수 있었다.

 

#include<iostream>
#include<queue>

#include<vector>
#define MAX_POS 100001
using namespace std;

int previous[MAX_POS];
bool visited[MAX_POS] = {false};
int n, k;
int result;
queue<pair<int, int>> q;            //first:pos second:dist
vector<int> path;

void bfs(){
    int pos, dist;
    while(!q.empty()){
        pos = q.front().first;
        dist = q.front().second;
        q.pop();
        if(pos == k){
            int t = pos;
            while(t != n){
                path.push_back(t);
                t = previous[t];
            }
            path.push_back(t);
            result = dist;
            return;
        }
        
        if (2 * pos < MAX_POS)
        {
            if (!visited[2 * pos])
            {
                visited[2 * pos] = true;
                previous[2 * pos] = pos;
                q.push({2 * pos, dist + 1});
            }
        }
        if(pos - 1 >= 0){
            if(!visited[pos-1]){
                visited[pos-1] = true;
                previous[pos-1] = pos;
                q.push({pos - 1, dist + 1});
            }
        }
        if(pos+1 < MAX_POS){
            if(!visited[pos+1]){
                visited[pos+1] = true;
                previous[pos+1] = pos;
                q.push({pos + 1, dist + 1});
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    q.push({n, 0}); 
    bfs();
    cout << result << "\n";
    for(int i = path.size()-1; i >= 0; i--){
        cout << path[i] << " ";
    }
    return 0;
}