BOJ 13549번 숨바꼭질3

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

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

 

숨바꼭질 문제 자체를 BFS 로 접근해야 하는 이유를 정확히 파악해보자면

가장 작은 간선(횟수)들로만 계속해서 연결해나가야 하기 때문에

현재 사용할 주어진 간선의 가중치가 동일하다는 전제조건이 있는 BFS 를 사용해야한다. 입니다

 

숨바꼭질3을 queue를 이용한 단순한 BFS 로 해결할 수 있을까? 에 대한 질문이 있다면

이 문제 자체는 문제의 특성 때문에 조건문만 잘 써준다면 우연히도 맞출 수 있게 됩니다.

그 우연한 조건이 *2 를 하고나서 +1 -1 순서로 queue 에 넣는것이 아닌 -1 +1 순서로 queue에 넣는 이유입니다.

어떤 경우에 +1 -1 이 오답처리가 되는지는 잘 모르겠습니다.

 

숨바꼭질3 같은 경우 *2 를 할때 간선(횟수)의 가중치가 0이 되게 됩니다.

BFS 를 하게 되면 다음으로 큰 가중치를 가진 간선을 push 하면서 맨뒤로 보내게 되는 과정을 알고 계실겁니다.

하지만 가중치가 0인 간선을 queue의 맨뒤로 보내면 이건 BFS 라고 할 수 없게 됩니다.

 

이 조건을 이용한다면 문제를 해결할 수 있게 됩니다.

가중치가 0인 간선을 queue의 back 이 아닌 front에 삽입할려면

list 형태의 queue 인 deque 를 이용하여 문제를 해결할 수 있게 됩니다.

 

#include <iostream>
#include <deque>
using namespace std;
 
int N, K;
deque<pair<int, int> > q;
bool visit[100001];
 
int main() {
    cin >> N >> K;
 
    int Min = 999999;
    q.push_back({ N,0 });
    while (!q.empty()) {
        int now = q.front().first;
        int cnt = q.front().second;
        q.pop_front();
 
        if (now > 100000 || now < 0) continue;
 
        if (visit[now]) continue;
        visit[now] = true;
 
        if (cnt > Min) continue;
        if (now == K) {
            Min = cnt;
            continue;
        }
 
        if (now != 0 && now < K) q.push_front({ now * 2, cnt });
        q.push_back({ now + 1,cnt + 1 });
        q.push_back({ now - 1,cnt + 1 });
    }
 
    cout << Min;
    return 0;
}