백준 1697 (숨바꼭질) c++

문제

1697번: 숨바꼭질

현재 위치 n이 주어지고 도착 지점 k가 주어지면 도착할때 까지 최단시간을 구하는 것입니다.

먼저 현재위치 n은 n+1로 가거나 n-1로 가거나 n*2로 갈 수 있습니다.

예를 들어 n = 5이고 k = 17이면

5 -> 10 -> 9 -> 18 -> 17 이므로 총 4초만에 최소시간으로 도달합니다.

 

단순히 문제를 봤을 때는 처음에는 dp를 생각하였습니다.

하지만 n이 움직일 수 있는 3가지 경우의 수에 대해서 따로따로 봐야하고

재귀함수로 구현해봤지만 메모리 초과가 났습니다.

 

다음에는 그래프 탐색으로 접근해봤습니다.

최단시간을 간선으로 생각하고 bfs탐색을 하였습니다.

범위는 100000입니다.

만약 탐색을 진행하다가 현재 위치가 80000이면 2 * 80000을 하면 1600000 이어서 Out of Bound가 됩니다.

따라서 발상을 전환해서 n부터 시작하는게 아니라 거꾸로 k부터 시작해서 n까지 도달하는 시간을 구하는 것입니다.

그렇게 되면 n+1 이 아니라 k-1 이되고 n*2가 아니라 k/2가 되고 n-1이 아니라 k+1이 됩니다.

또한 이미 방문한 정점은 체크해 줍니다. 만약 체크를 안해주면 cycle이 돌게 되어 무한 시간 초과가 납니다.

ex) 4 -> 3 -> 2 -> 4

bfs를 진행하기 위한 큐에는 

{k, 시간} 이 들어갑니다.

12번째 줄을 보면 현재 위치 x는

2의 배수 여야만 x/2가 됩니다.

따라서 처리한 코드입니다.

 

 

 

 

 

 

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<set>
#include<tuple>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int n, k;
bool visit[100001];
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n >> k;
    queue<pair<int,int>>q;
    q.push({ k, 0 });
    int cnt;
    while (!q.empty()) {
        int x = q.front().first;
        int time = q.front().second;
        visit[x] = true;
        if (x == n) {
            cnt = time;
            break;
        }
        q.pop();
        if(!visit[x-1])
            q.push({ x - 1, time + 1 });
        if (x % 2 == 0 && !visit[x / 2])
            q.push({ x / 2, time + 1 });
        if(!visit[x+1])
            q.push({ x +1, time + 1 });
    }
    cout << cnt;
 
    return 0;
}