13913_숨바꼭질4

제가 2일 동안 고민해봤고 선생님의 논리와 같은 거 같은데 왜 안 풀리는지 모르겠습니다.

숨바꼭질2에서는 답이 잘 나와서 확인 해봤는데 

(방금 고민하면서 문제 풀어버렸습니다. 그렇지만 질문은 있습니다.)

//cout << s <<" "; 이거 있는 부분을 해제하고 실행하면 괴상한 수를 잔뜩 거쳐서 목적지로 가더라고요.

이거 제 머리속에 있는 bfs 논리로는 괴상한 수들을 거칠 이유가 없습니다.

 

또

우선 dfs를 이용해서 경로 추적할 수 있을 거 같은데 그 방향은 안 되는 건가요?

 

 

#include<bits/stdc++.h>

using namespace std;

#define INF 987654321

int n, k, ret = INF, cnt;

const int jump[] = {-1, 1, INF};

int visited[100004];

int parent[100004];

void printPath(int i){

if(parent[i] == -1){

return;

}

printPath(parent[i]);

cout << i << " ";

}

 

 

void bfs1D(int s){

visited[s] = 1;

queue<int> q;

q.push(s);

int ns =-1;

parent[s] = -1;

while(!q.empty()){

int here = q.front(); q.pop();

//cout << s << " ";

if(here==k){

cnt++;

ret = visited[here]-1;

break;

}

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

if(i==2){

ns = 2*here;

}else{

ns = here + jump[i];

}

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

if(visited[ns]==0){

visited[ns] = visited[here]+1;

q.push(ns);

parent[ns] = here;

}

}

}

cout << ret << '\n';

cout << s << " ";

printPath(k);

}

 

 

int main(){

ios_base::sync_with_stdio(false);

cin.tie(0); cout.tie(0);

cin >> n >>k;

bfs1D(n);

 

}