[13549번] 숨바꼭질 3

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

수빈이가 동생 위치에 도달하기까지 주어진 조건을 만족하며 최소로 걸리는 시간을 구하는 문제입니다.

 

수빈이의 현재 위치를 x라고 할 때, 움직일 수 있는 행동으로는

1. 순간이동 x → 2 * x (소요시간:0초)

2. 앞으로 이동 x → x + 1 (소요시간:1초)

3. 뒤로 이동 x → x - 1 (소요시간:2초)

이렇게 3가지 입니다.

 

우선, 수빈이의 처음 시작 위치는 0초 걸리기 때문에 q에 넣어주었습니다.

모든 행동들이 동일한 가중치(1초)를 가졌다면 하나의 큐로 해결할 수 있을 것입니다.

문제가 되는 순간이동은 0초가 걸리기 때문에 앞 뒤로 이동하여 1초가 걸리는 행동과 동일한 큐에 넣으면 안되고 다른 큐에 넣어주어야 합니다.

0초로 도달할 수 있는 거리들을 먼저 처리하고  그 다음 1초 처리하는 이런 순으로요.

그래서 큐를 2개를 선언하고 0초가 걸리는 행동을 q에, 1초가 걸리는 행동은 nq에 넣습니다.

그럼 q에는 순간 이동하여 도달할 수 있는 수빈이의 위치들만이 들어가게 됩니다.

소요시간이 0초인 거리들을 BFS하다가 q가 비어있게 되면 아까전에 1초가 걸리게 되는 위치들을 넣어두었던 nq를 q에 대입하고 nq는 새로운 큐 객체를 대입해줍니다. 0초 큐가 이제는 1초큐가 되고, 1초큐는 이제는 2초에 도달하는 거리들을 다루게 됩니다.

 

조심해야할 부분은 while 문 안에서 순간이동의 If문은 반드시 먼저 나와야 합니다.

왜냐하면 수빈이의 위치가 1일 때 2로 가는 최소 시간은 순간이동을 사용하여 0초가 되어야 하는데, 1 증가하는 조건이 먼저 나오게 되면 1초가 되면서 방문처리 완료가 되기 때문에 최소시간을 구할 수 없기 때문입니다.

 

수빈이와 동생이 위치할 수 있는 점의 최대 값 MAX를 10만으로 지정했는데, 굳이 수빈이가 2배 거리로 순간이동한다고 해서 20만으로 설정할 필요는 없습니다.

실제 동생이 위치할 수 있는 거리가 10만까지이기 때문에 10만까지의 정점만 방문해보면서 최단 시간을 구하면 됩니다.

 

[코드1]

#include <queue>
#include <iostream>
using namespace std;
const int MAX = 100000;
int d[MAX + 1];
bool c[MAX + 1];
int main () {
    int n, k;
    cin >> n >> k;
    queue<int> q;
    queue<int> nq;
    q.push(n);
    d[n] = 0;
    c[n] = true;
    while (!q.empty()) {
        int x = q.front(); q.pop();
        if (x * 2 <= MAX && c[x * 2] == false) { //2배 조건은 반드시 먼저 나와야 함.
            q.push(x * 2);
            c[x * 2] = true;
            d[x * 2] = d[x];
        }
        if (x + 1 <= MAX && c[x + 1] == false) {
            nq.push(x + 1);
            c[x + 1] = true;
            d[x + 1] = d[x] + 1;
        }
        if (x - 1 >= 0 && c[x - 1] == false) {
            nq.push(x - 1);
            c[x - 1] = true;
            d[x - 1] = d[x] + 1;
        }
        if (q.empty()) {
            q = nq;
            nq = queue<int>();
        }
    }
    cout << d[k] << '\n';
    return 0;
}

 

[결과]

5 17 //input
2

 

 

 

코드1은 큐를 2개를 사용했었다면, 코드2는 덱(deque) 하나를 가지고도 구현 할 수 있는데요.

0초가 걸리는 위치는 덱의 앞에, 1초가 걸리는 위치는 덱의 뒤에 넣어주면서 BFS를 진행하면, 간단하게 구현이 됩니다.

 

[코드2]

#include <deque>
#include <iostream>
using namespace std;
const int MAX = 100000;
int d[MAX + 1];
bool c[MAX + 1];
int main () {
    int n, k;
    cin >> n >> k;
    deque<int> q;
    q.push_front(n);
    c[n] = true;
    d[n] = 0;
    while(!q.empty()) {
        int x = q.front();
        q.pop_front();
        if (x * 2 <= MAX && c[x * 2] == false) {
            q.push_front(x * 2);
            d[x * 2] = d[x];
            c[x * 2] = true;
        }
        if (x + 1 <= MAX && c[x + 1] == false) {
            q.push_back(x + 1);
            d[x + 1] = d[x] + 1;
            c[x + 1] = true;
        }
        if (x - 1 >= 0 && c[x - 1] == false) {
            q.push_back(x - 1);
            d[x - 1] = d[x] + 1;
            c[x - 1] = true;
        }
    }
    cout << d[k] << '\n';
    return 0;
}

[결과]

5 17 //input
2