Boj 12851 & 13913 c++ 숨바꼭질 2, 4

원래의 문제에서 약간 달라진 문제들이다. 

숨바꼭질 2는 최단 경로의 수를 구해야 하는 문제이며, 

숨바꼭질 4는 최단경로를 그대로 출력해야 하는 문제이다.

 

코드는 다음과 같다.

 

*숨바꼭질 2

#include<iostream>
#include<vector>
#include<queue>
#define Max 100001
using namespace std;
vector<int> dist(Max, -1);
vector<int> cnt(Max);
queue<int> q;

void BFS(int start){

 int cur, nx;
 dist[start]=0;
 cnt[start]=1;
 int dx[3]={-1, 1,};
 q.push(start);

 while(!q.empty()){
    cur=q.front();
    for(int i=0; i<3; i++){
        (i==2)? nx=cur*2 : nx=cur+dx[i];

        if(nx<0 || nx>100000)
            continue;

        if(dist[nx]==-1){
            dist[nx]=dist[cur]+1;
            cnt[nx]=cnt[cur];
            q.push(nx);
        } else if (dist[nx]==dist[cur]+1){
            cnt[nx]+=cnt[cur];
        }

    }
    q.pop();
 }



}

int main(){

    int N, K;

    cin>>N>>K;

    if(N==K){
        cout<<"0\n1";
        return 0;
    }

    BFS(N);

    cout<<dist[K]<<"\n"<<cnt[K];

}

dist벡터의 초기값을 -1로 설정하여 visited 벡터를 대체하였다. -1로 인해 횟수가 왜곡되는 것은  -1이 연산에 반영되지 않기에 안심해도 된다. 최단 경로의 가짓수를 구하는 방법은 기억해두면 좋을 듯 싶다. 해당 노드를 처음 방문했을 경우에는 경로의 수를 누적하지 않지만 이미 방문하였음에도 최단 경로인 경우에는 그 노드까지의 가짓수를 누적해준다. 이미 방문한 경우에는 큐에 넣어주지 않아도 된다. 이해가 안간다면 입력예제 5 17을 생각해보면 편하다. 17이 두번 방문되지만 이전 노드와는 최단 경로이므로 그 전까지의 경우를 한번 더해주는 것이다. 이렇게 경로를 구하고 출력해주면 코드는 끝난다.

 

* 숨바꼭질 4

 

#include <iostream>
#include <vector>
#include <queue>
#define Max 100001
using namespace std;

vector<int> bk(Max, -1);
vector<int> dist(Max);
vector<int> visited(Max);
vector<int> path;
queue<int> q;

void BFS(int start, int goal){
    int nx;
    int dx[2]={-1, 1,};
    q.push(start);
    visited[start]=1;

    while(!q.empty()){
        int start=q.front();
        for(int i=0; i<3; i++){
            (i!=2)? nx=dx[i]+start : nx=start*2;
            if(nx<0 || nx>=Max)
                continue;
            if(!visited[nx]){
                q.push(nx);
                dist[nx]=dist[start]+1;
                bk[nx]=start;
                visited[nx]=1;}

            if(nx==goal)
                return;
        }
        q.pop();

    }

}

int main(){
    int N, K;
    cin>>N>>K;
    if(N==K){
        cout<<"0\n"<<K;
        return 0;
    }

    BFS(N, K);
    cout<<dist[K]<<"\n";
    for(int cur=K; cur!=-1; cur=bk[cur]){
        path.push_back(cur);
    }
    for(int i=path.size()-1; i>=0; i--){
        cout<<path[i]<<" ";
    }

}

 

이코드는 숨바꼭질 2보다 논리가 간단하지만 생각해내기가 어려워 구글링을 하였다. 이전 노드의 인덱스 만을 연속해서 참조하고, 이를 거꾸로 출력하는 것이 전부이다.