[Baekjoon] 백준 14549번 숨바꼭질3

14549번 숨바꼭질3 문제 풀이

문제

• 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
  수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

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

출력

• 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제

입력
5 17 

출력
2

코드

deque 사용

#include<iostream>
#include<algorithm>
#include<deque>
#include<vector>
#include<queue>
using namespace std;

const int MAX = 100001;
int road[MAX];
bool check[MAX];

int main() {
    deque <int> dq;
    int n, k;
    cin >> n >> k;
    road[n] = 0;
    check[n] = true;
    dq.push_back(n);
    while (!dq.empty()) {
        int nx = dq.front();
        dq.pop_front();
        if (nx * 2 < MAX && check[nx * 2] == false) {
            dq.push_front(nx * 2);
            road[nx * 2] = road[nx];
            check[nx * 2] = true;
        }
        if (nx + 1 < MAX && check[nx + 1] == false) {
            road[nx + 1] = road[nx] + 1;
            check[nx + 1] = true;
            dq.push_back(nx + 1);
        }
        if (nx - 1 >= 0 && check[nx - 1] == false) {
            road[nx - 1] = road[nx] + 1;
            check[nx - 1] = true;
            dq.push_back(nx - 1);
        }
    }
    cout << road[k] << "\n";
    return 0;
}

두 개의 queue 사용

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

int n, m;
const int MAX = 100001;
int road[MAX];
bool check[MAX];

int main() {
    cin >> n >> m;
    road[n] = 0;
    check[n] = true;
    queue<int> q;
    queue<int> next_q;
    q.push(n);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        if (now * 2 < MAX && check[now*2] == false) {
            road[now * 2] = road[now];
            check[now * 2] = true;
            q.push(now * 2);
        }
        if (now - 1>=0&& check[now -1] == false) {
            road[now - 1] = road[now] + 1;
            check[now - 1] = true;
            next_q.push(now - 1);
        }
        if (now + 1 < MAX&& check[now + 1] == false) {
            road[now + 1] = road[now] + 1;
            check[now + 1] = true;
            next_q.push(now + 1);
        }
        if (q.empty()) {
            q = next_q;
            next_q = queue<int>();
        }
    }
    cout << road[m] << endl;
}

해결방법

deque 사용

• deque는 queue의 front와 end위치를 직접 선택하여 데이터를 넣을 수 있다.
• 따라서 순간이동을 하는 경우 deque의 push_front()를 사용하여 queue의 앞에 데이터를 넣어준다.
• 그 밖의 경우에는 push_back()을 사용하여 뒤에 데이터를 넣어주게된다.
• 코드를 작성할 때 순간이동을 하는 경우를 가장 먼저 queue에 넣어주지 않으면 원하는 결과 값을 도출할 수 없다.

두 개의 queue 사용

• 순간이동을 하는 경우의 데이터를 저장시키는 경우와 나머지 경우의 데이터를 저장시킬 queue 두 개를 생성한다.
• 순간이동을 하는 경우의 queue, 즉 코드내에서 q에 넣어져있는 데이터가 우선이기 때문에 항상 q.front()를 사용하여 데이터를 꺼내준다.
• 만약 q에 데이터를 모두 꺼냈을 경우에는 후순위인 next_q에 저장되어있는 데이터를 q로 옮겨와서 진행하면 된다.