13913 숨바꼭질4

숨바꼭질 4 성공스페셜 저지

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	4046	1349	939	32.994%

문제

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

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

입력

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

출력

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

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

하아.. 힘들게 풀었다.

최단거리만 구하다가 최단경로 출력하는 것에서 당황해서 시간버렸고

또 -1한 노드를 체크하는 조건을 <MAX로 줘버려서 음수까지 내려가버린것을 모르고 계속 얼탔다.

최단경로는 그냥 넣을때 그 값을 인덱스로하는 배열의 값에 이전노드를 넣어주기만 하면된다.

어짜피 1번만 방문할 것이기 때문에 중복되지 않는다

다음엔 꼭 조심하자.

#include <bits/stdc++.h>

using namespace std;

#define MAX 100001

int N,K;

bool visited[MAX];

int pre_node[3][MAX];

queue<int> que;

int bfs();

int main(){

freopen("input.txt","r",stdin);

cin>>N>>K;

memset(visited, false, sizeof(visited));

memset(pre_node, -1, sizeof(pre_node));

visited[N] = true;

que.push(N);

//pre_node[0][0][N] = pre_node[1][0][N] = pre_node[2][0][N] = -1;

int total_step = bfs();

cout<<total_step<<"\n";

vector<int> path;

path.push_back(K);

int temp = K;

while(total_step--){

for(int i=0; i<3; i++){

if( pre_node[i][temp] != -1 ){

temp = pre_node[i][temp];

path.push_back(temp);

}

}

}

for(int i=path.size()-1; i>=0; i--){

cout<<path[i]<<" ";

}

return 0;

}

int bfs(){

int temp=0;

int total_step=0;

int step_size=0;

while(!que.empty()){

step_size = que.size();

total_step++;

for(int i=0; i<step_size; ++i){

temp = que.front();

que.pop();

if( temp == K ){

return total_step-1;

}

if( temp+1<MAX && !visited[temp+1] ){

que.push(temp+1);

visited[temp+1] = true;

pre_node[0][temp+1] = temp; // temp is only one visited. So, save preNode

}

if( temp-1>=0 && !visited[temp-1] ){

que.push(temp-1);

visited[temp-1] = true;

pre_node[1][temp-1] = temp;

}

if( temp*2<MAX && !visited[temp*2] ){

que.push(temp*2);

visited[temp*2] = true;

pre_node[2][temp*2] = temp;

}

}

}

return -1;

}