개발 블로그

문제 링크 : www.acmicpc.net/problem/13913

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

접근 방법

BFS로 한 스템씩 나아가면서 visited[]에 직전에 지났던 위치를 저장한다. 

visited[]는 처음에 시작점을 제외하고 -1로 초기화 시켰기 때문에 위치를 지정하면 동시에 방문여부도 체크할 수 있다.

stop 조건에 걸리면 visited[] 를 거꾸로 타고 올라가면서 지나온 자리를 resVec에 push 한다.

그리고 main()에서 resVec을 거꾸로 출력한다.

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

using namespace std;

int N, K;
int visited[100001];
queue<int> que;
vector<int> resVec;

void BFS(){
    
    que.push(N);
    
    while(!que.empty()){
        
        int now = que.front();
        que.pop();
        
        if(now==K){
            resVec.push_back(now);
            while(visited[now]!=100001){		   //처음 시작점까지 갈 때 까지
                resVec.push_back(visited[now]);   //거꾸로 타고 올라가면서 지나온 자리 push
                now = visited[now];
            }
            return;
        }
        
        
        if(visited[now-1]==-1 && 0<=now-1 && now-1<=100000){	//방문체크 and 범위체크
            visited[now-1] = now;		//바로 직전에 지나온 자리 저장
            que.push(now-1);			
        }
        if(visited[now+1]==-1 && 0<=now+1 && now+1<=100000){
            visited[now+1] = now;
            que.push(now+1);
        }
        if(visited[2*now]==-1 && 0<=2*now && 2*now <= 100000){
            visited[2*now] = now;
            que.push(2*now);
        }
    } 
}

int main(){
   
    cin >> N >> K;
    memset(visited, -1, sizeof(visited));
    visited[N] = 100001;		//시작 지점 체크를 위함
    
    BFS();
    cout << resVec.size()-1 << "\n";
    
    for(int i = resVec.size()-1; i>=0; i--){
        printf("%d ", resVec[i]);
    }
    
    return 0;
}