백준 No.13549 [숨바꼭질3]

Baekjoon Online Judge No.13549 [숨바꼭질3]

---

 Problem 

13549번: 숨바꼭질 3

---

 Code 

#include <iostream>
#include <vector>
#include <queue>
#define pos first
#define time second
 
using namespace std;
typedef pair<int, int> PII;
 
const int MAX = 100000;
 
int subin, dong;
queue<PII> Q;
vector<bool> visited(MAX + 1, false);
 
int main() {
    cin >> subin >> dong;
 
    Q.push({ subin, 0 });
    visited[subin] = true;
 
    while (!Q.empty()) {
        PII temp = Q.front();
        Q.pop();
 
        int& POS = temp.pos;
        int& TIME = temp.time;
        visited[POS] = true;
 
        if (POS == dong) {
            cout << TIME;
            break;
        }
        
        // session #1
        int curPos = 2 * POS;
        while (curPos <= MAX && curPos && !visited[curPos]) {
            Q.push({curPos, TIME });
            curPos *= 2;
        } // ok
 
        // session #2
        // if (2 * POS <= MAX && !visited[2 * POS]) Q.push({ 2 * POS, TIME }); // no
 
        if (POS < MAX && !visited[POS + 1]) Q.push({ POS + 1, TIME + 1 });
        if (POS > 0 && !visited[POS - 1]) Q.push({ POS - 1, TIME + 1 });
    }
}

---

 How to solve 

  기존 BFS 문제에서 약간의 컨트롤을 요구하는 문제였다.

 

  queue를 이용한 BFS는 queue의 특성상 그때그때의 queue.front() 만 참고할 수 있다. 따라서 queue는 문제 기준 time이 적은 것부터 들어가야 한다.

 

  x → x + 1, x → x - 1 의 경우엔 시간이 1 늘어나지만 순간이동 하는 경우( x → 2*x )는 시간이 늘어나지 않는다. 따라서 이 순간이동 하는 경우는 좌우로 한 칸 이동하는 경우보다 우선순위를 가진다.

 

  따라서 일반적인 문제였다면 위 코드의 주석처리된 session #2 처럼 하면 됐겠지만, session #1 처럼 while 문을 사용하여 가능한 곳 까지 순간이동을 해 주었다.

 

  그리고, 처음에는 메모리 초과가 떴었는데, 이 문제는 x의 값이 증가하기만 하는것이 아닌 감소하는 경우도 발생하므로 visited 변수를 사용하지 않으면 queue에 엄청나게 많은 값이 들어가기 때문에 발생하였던 문제였다. 따라서 visited vector 도 사용해 주어 이미 방문한 점이면 queue에 push 하지 않도록 하였다.

---

+ 다익스트라를 이용해서도 풀 수 있을 것 같다. 0 부터 100,000 까지의 정점 x가 있고, x → x + 1, x → x - 1 의 경우에 간선의 가중치는 1, x → 2*x  의 경우의 간선의 가중치는 0으로 해서 풀면 될 것 같다.