[백준] 13913번 숨박꼭질4(c++)

문제 및 입출력

문제 접근

그래프 문제이다.
0과 1을 제외한 노드들은 3개의 노드들과 연결되어 있다. 그래서 해당 노드들을 탐색하면 되는 문제였다.
최소 경로를 구하는 것이기 때문에, bfs를 사용해서 하면 되었다. 탐색하다가 목적지에 도착을 하면 해당 경로가 가장 짧은 경로이기 때문이다.
어느 경로를 통해서 가는 지는 union find처럼 자신의 node의 parent가 누군지 구해서 경로를 저장하였다.

코드 구현(c++)

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <stack>

#define MAX 100001

using namespace std;

bool check[MAX];
int parent[MAX];

int N,K;

stack<int> res;
int res_num;

void bfs(){
    //먼저 N을 넣기.
    queue<pair<int, int> > q;
    q.push(make_pair(N,0));
    parent[N] = N;
    check[N] = true;
    while(!q.empty()){
        int cur = q.front().first;
        int num = q.front().second;
        q.pop();
        if(cur == K){
            while(parent[cur] != cur){
                //stack에 cur을 넣고, cur = parent[cur];
                res.push(cur);
                cur = parent[cur];
            }
            res.push(cur);
            res_num = num;
            break;
        }
        //next 3개 cur+1 cur-1 cur*2
        int next_1 = cur + 1; int next_2 = cur - 1 ; int next_3 = cur * 2;
        if(next_1 >= 0 && next_1 <= MAX-1 && !check[next_1]){
            q.push(make_pair(next_1,num+1));
            parent[next_1] = cur;
            check[next_1] = true;
        }
        if(next_2 >= 0 && next_2 <= MAX-1 && !check[next_2]){
            q.push(make_pair(next_2,num+1));
            parent[next_2] = cur;
            check[next_2] = true;
        } 
        if(next_3 >= 0 && next_3 <= MAX-1 && !check[next_3]){
            q.push(make_pair(next_3,num+1));
            parent[next_3] = cur;
            check[next_3] = true;
        }  
    }
}

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

    cin >> N >> K;

    memset(check,false,sizeof(check));
    bfs();
    cout << res_num << "\n";
    while(!res.empty()){
        cout << res.top() << " ";
        res.pop();
    }
}