[백준] 13913번 숨바꼭질4

13913 숨바꼭질4

문제

---

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

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

입력

---

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

출력

---

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

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

---

풀이)

bfs를 이용했고, 한번 확인했던 숫자는 중복처리 해줘서 다시 계산하지 않게끔 푼 문제이다.

+ 경로를 출력하기 위해 경로 저장할 배열을 하나 선언해서 풀었다.

int parent[]; 

//parent[i] = j ⇒ j를 통해 i로 이동했다는 뜻 

주의사항

N == K일때, N 또는 K 하나만 경로로 출력해준다.

코드)

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
#define INF 2000001
int N, K;
bool visited[INF];
int parent[INF];
 
int main() {
    scanf("%d %d", &N, &K);
    if (N == K) {
        printf("0\n");
        printf("%d", N);
        return 0;
    }
    for (int i = 0; i < INF; i++) {
        parent[i] = i;
    }
    queue<int> qu;
    qu.push(N);
    visited[N] = true;
    int cnt = 0;
    bool suc = false;
    while (!qu.empty())
    {
        int size = qu.size();
        while (size--)
        {
            int here = qu.front();
            qu.pop();
            if (here == K) {
                suc = true;
                break;
            }
            //뒤로
            int next = here - 1;
            if (next >=0 && !visited[next]) {
                parent[next] = here;
                visited[next] = true;
                qu.push(next);
            }
            //앞으로
            next = here + 1;
            if (next < INF && !visited[next]) {
                parent[next] = here;
                visited[next] = true;
                qu.push(next);
            }
            //순간이동
            next = here * 2;
            if (next < INF && !visited[next]) {
                parent[next] = here;
                visited[next] = true;
                qu.push(next);
            }
        }
        if (suc) break;
        cnt++;
    }
    vector<int> path;
    printf("%d\n", cnt);
    for (int i = K; i != parent[i]; i = parent[i]) {
        path.insert(path.begin(), i);
    }
    path.insert(path.begin(),N);
    for (int i = 0; i < path.size(); i++) {
        printf("%d ", path[i]);
    }
    return 0;
}

+) 경로 저장시에 insert()함수를 이용해서 앞에서부터 경로 삽입하게 해줬는데

    다른 방법으로는, 그냥 push_back()함수를 이용해 뒤에서부터 삽입한 후

    reverse()함수를 통해 경로를 역전시키면 된다.

    //reverse(path.begin(), path.end())