BOJ 13913 숨바꼭질 4 C++

 

13913번: 숨바꼭질 4

수빈이의 좌표가 n으로 주어지고, 동생이 있는 좌표 k가 주어지면, 

수빈이가 한칸 앞 뒤, 그리고 현재 좌표의 두배의 위치로 이동할 수 있다.

BFS를 통해서 해결하였는데, 다른 문제들과는 다르게 현재까지 거쳐왔던 경로를 출력하는

문제여서 포스팅하고, 또 처음 해결할 때는 여러 if문을 작성하여 BFS를 수행했으나

for문의 다른 문법을 통해서 하나로 처리하는 방법에 대해서 공부하게 된 문제이다.

 

또 거쳐왔던 경로를 출력하는 방법으로, 부모를 거쳐가는 방법이 있고,

첫 노드는 부모를 자기자신으로 두어 부모가 자기자신이 될 때까지 

deque를 이용해 제일 앞에 좌표를 삽입하고

for반복문을 통해서 출력하면 된다.

 

deque를 초기화 할때 중괄호 {} 를 통해서 초기화 할 수 있다는 점도 기억해두자.

 

#include <bits/stdc++.h>
using namespace std;

int board[100003];
int prePos[100003];
int sis, bro;
queue<int> Q;

int main(){
    cout.sync_with_stdio(0);
    cin.tie(0);

    cin >> sis >> bro;
    board[sis] = 1;
    prePos[sis] = sis;
    Q.push(sis);
    while(!board[bro]) {
        int v = Q.front(); Q.pop();
        for(int nv: {v+1, v-1, 2*v}) {
            if(nv < 0 || 100001 <= nv) continue;
            if(board[nv]) continue;
            board[nv] = board[v] + 1;
            prePos[nv] = v;
            Q.push(nv);
        }
    }
    
    cout << board[bro] - 1; << '\n';
    deque<int> track = {bro};
    while(track.front() != sis) {
        track.push_front(prePos[track.front()]);
    }
    for(int p: track) cout << p << ' ';

    return 0;
}