BOJ 1697번 숨바꼭질

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

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

 

숨바꼭질 같은 경우의 문제는

DFS 보다는 BFS 를 통해서 문제를 해결하여야 합니다.

방문처리를 확인해주는 것은 필수이고, +1 -1 *2 의 순서를 어떻게 줘야할지 고민했는데

*2 같은 값의 변화가 큰 것 부터 주는 것이 맞다고 생각해서 아래와 같이 구현하였고

 

처음에 생각했던 것은 queue 로부터 가장 먼저 발견됬다고 해도

이게 가장 적은 횟수일 보장이 있을까 하는 생각에 저런식으로 구현하였는데

포스팅을 하면서 생각해보니 now == K 가 성립되는 것은

가장 먼저 발견된 것이니 애초에 나머지 큐에 있는 것이 현재 cnt 보다 적을수가 없다는게 성립되고,

continue 가 아니라 break; 를 해주시는게 시간상 빠를 것 같습니다.

 

#include <iostream>
#include <queue>
using namespace std;
 
int N, K;
queue<pair<int, int> > q;
bool 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 (visit[now]) continue;
        visit[now] = 1;
 
        if (cnt >= Min) continue;
        if (now == K) {
            Min = cnt;
            continue;
        }
 
        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;
    return 0;
}