BOJ 12851번 숨바꼭질2

BOJ : https://www.acmicpc.net/problem/12851

github : https://github.com/junho0956/Algorithm/blob/master/12851/12851/%EC%86%8C%EC%8A%A4.cpp

 

이 문제를 해결할 수 있는 방법은 2가지가 있을 것 같습니다.

1. 가장 정확한 방법

숨바꼭질(1697번) 문제를 생각해보면

큐에서 넣는 3가지 작업을 거치기 전에 방문배열을 확인해서 이미 방문했으면 패스하는 조건을 쓰게 됩니다.

하지만 이 경우 임의의 수가 *2, +1, -1 의 작업을 했을 때 같은 값을 가지게 된다면?

한가지 조건만 사용하게 되고 나머지는 사용하지 않게 될 것입니다.

숨바꼭질2 의 중요포인트는 이 부분이고, 이 부분을 해결하기 위해서는

큐에서 꺼낸 후에 pop 을 하면서 방문처리를 해주는 것+방문확인은 안하는 것 입니다.

 

좀더 정확히 말하자면 지금 사용할 값을 바로 방문처리 해주는 것입니다.

예를 들면 1->4 를 만들기 위해서는 

1 -> 2(+1) -> 4

1 -> 2(*2) -> 4

이 2가지 방법을 사용해야하고,

만약 큐에서 2를 꺼냈는데 방문을 확인해버리게 되면 +1 또는 *2 중 1개를 확인하게 되고

다음 큐에서 2를 꺼냈을 때는 방문한 것으로 확인하고 넘어가버리게 되서 나머지 1개를 확인하지 못하게 됩니다.

 

그러므로 2를 꺼내서 바로 방문처리를 해주고 확인은 하지않는다면? 

=> 2(+1)을 먼저 꺼냈다고 해도 큐에는 아직 2(*2) 가 남아있고

다음에 2(*2) 를 꺼내도 이미 방문은 했지만 확인은 하지 않으니 2(*2) 도 사용할 수 있게 되는 것입니다.

 

 

2. 편법을 통해서.. 문제를 해결할 수 있습니다.

애초에 어떤 임의의 수를 만들 수 있는 방법은 *2, +1, -1 이 있으니

아무리 많아도 3가지 일 것입니다.

방문배열을 체크만 하는 것이 아닌, 몆번 방문했는지 확인한다면

3번 을 초과해서 방문할 일은 없어집니다.

 

if (visit[now] > 3) continue;

visit[now]++;

 

의 코드를 사용한다면.. 1번 방법을 모르더라도 10만정도의 범위를 해결하는데는 무리가 없습니다 ㅎㅎ...

 

#include <iostream>
#include <queue>
using namespace std;
 
int N, K, check;
queue<pair<int, int> > q;
int visit[100001];
 
int main() {
    cin >> N >> K;
 
    int Min = 999999;
    q.push({ N,0 });
    while (!q.empty()) {
        int now = q.front().first;
        int cnt = q.front().second;
        q.pop();
 
        if (now > 100000 || now < 0) continue;
 
        if (cnt > Min) continue;
        if (now == K) {
            Min = cnt;
            check++;
            continue;
        }
 
        if (visit[now] > 3) continue;
        visit[now]++;
 
        if (now != 0 && now < K) q.push({ now * 2, cnt + 1 });
        q.push({ now + 1,cnt + 1 });
        q.push({ now - 1,cnt + 1 });
    }
 
    cout << Min << '\n' << check;
    return 0;
}