[백준] 13913번. 숨바꼭질4

[문제]

 

www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

 

[풀이]

 

수빈이의 위치 N, 동생의 위치 K가 입력으로 주어지고 수빈이가 동생을 찾는 최단경로를 구하는 문제.

이 때, 수빈이는 현재 위치 X 에서 X-1,X+1,2*X로만 움직일 수 있다.

 

최단경로를 찾아야 하므로 BFS를 사용했다.

현재 위치 X에서  X-1,X+1,2*X로 움직이도록 하였고 visited 배열을 사용해 재방문 하지 않도록 했다.

또한 경로도 구해야 parent 배열을 사용해 해당 index에 오기 전 index 값을 저장했다.

 

처음의 input의 범위가 0부터 100,000 사이라서 MAX 값을 100,001로 설정하였는데

5001 100000과 같은 경우 

 

최단 경로를 구하기 위해 100,000을 넘어가는 경우도 있으므로 MAX 값을 200,001로 변경하였다.

 

 

[코드]

 

시간 : 20 ms

 

#include <iostream>
#include <queue>
#define MAX 200001

using namespace std;

int n[2] = {-1,1};
int visited[MAX]={0,};
int parent[MAX]={0,};
int N,K;
vector <int> ans;

void bfs()
{
    queue<int> q;
    q.push(N);
    
        int idx = q.front();
        q.pop();
        
        if(idx == K ){
            cout << visited[idx] << "\n";
            while(idx != N){
                ans.push_back(idx);
                idx= parent[idx];
            }
            ans.push_back(N);
            return ;
        }
        for(int i=0;i<3;i++){
            int nidx =0;
            if(i==2)    nidx = idx*2;
            else nidx = idx+n[i];
            
            if(nidx < 0 || nidx > MAX || visited[nidx] ) continue;
            
            q.push(nidx);
            visited[nidx]=visited[idx]+1;
            parent[nidx] = idx;
        }
    }

int main(void)
{
    cin >> N >> K;
    bfs();
    int _size = ans.size()-1;
    for(int i=_size; i>=0 ; i--)
        cout << ans[i]<< " ";
    return 0;
}