BOJ 1697, 숨바꼭질

이 문제는 BFS(너비 우선 탐색)을 이용한 풀이입니다. 약간의 memoization도 포함되어 있습니다. 

보통 아시기엔, BFS는 그래프 위에서 사용하는 것이라고 알고 있습니다.

그래프가 없는데 BFS를 어떻게 사용해야 할까요?

풀이는 다음과 같습니다. 주는 상태에 따라 그래프를 생성하면 되는 것입니다. 인접행렬이 아닌 Vertex와 Vertex의 연결 관계를요!

자 그럼 예제를 통해 방법을 소개하겠습니다.

예제 입력 

5 17

예제는 5에서 출발할 때, 17을 찾는 가장 빠른 방법을 물어보고 있습니다.

5에서 출발하니 처음 정점을 다음과 같이 생성합니다.

<0초>

<1초>

<2초>

<3초>

<4초>

4초가 걸려서 17로 이동할 수 있었습니다 ! 다른 간선들도 그려보면 좋지만, 그래프가 너무 복잡해져서 그리지 않았습니다.

이 그래프는 인접행렬이나 인접 List로 풀지 않습니다. Queue와, Memoization을 이용한 BFS로 해결할  수 있습니다.

<알고리즘>

1) 1부터 100000까지의 숨바꼭질 상태가 있으니, int형 배열 memo[200001]을 선언한 후, INT_MAX나 987654321같은 매우 큰 수로 초기화 해 줍시다.(20만인 이유는 10만까지 가서 *2를 해버릴 수 있으므로, 안전하게.)

2) 처음 입력으로 주어진 수(예제에서는 5) memo[5] = 0을 대입해 줍시다.

3) 5를 queue에 넣습니다 (BFS 시작)

4) 큐의 front를 pop 한 후, memo[(front의 값-1)], memo[(front의 값+1)], memo[(front의 값*2)]에 memo[(front의 값)]+1을 대입해줍니다. 즉 예제에서 첫 번째 경우의 수는

memo[4] = memo[5]+1;

memo[6] = memo[5]+1;

memo[10] = memo[5]+1;이 되겠습니다.

5) 그럼 다시 front의 값-1, front의 값+1, front의 값*2를 queue에 넣어주고, 4)를 반복합니다.

4)를 반복하면 그다음엔 

memo[3] = memo[4]+1 (=memo[5]+2)

memo[5] = memo[4]+1 (=memo[5]+2)

memo[8] = memo[4]+1 (=memo[5]+2)

가 되겠습니다.

단, 주의할 것은 memo[x]에 INT_MAX나 987654321 이외의 값이 들어있다면, 값을 대입하지 말아야합니다. 왜냐하면 가려고 하는 vertex에 도달할 수 있는 시간이, 지금 대입하려는 시간보다 짧기 떄문입니다.

그 예시가 바로 memo[5] = memo[4]+1입니다.

정 불안하다면, memo[5] = min(memo[5], memo[4]+1)로 대입하시면 됩니다.

이렇게해서 문제를 풀고 나면, BFS의 시간복잡도가 O(NlogN)이므로, N이 10만이기 때문에 충분히 시간 안에 문제를 해결할 수 있습니다.

다음은 BFS를 통한 문제풀이의 소스코드입니다.

#include <iostream>
#include <queue>
#include <cstdio>
 
using namespace std;
 
typedef long long LL;
bool visit[100001] = { false, };
int nth[100001] = { 0, };
 
int main() {
    queue<int> q;
    int n, k;
    for (int i = 0; i <= 100000; i++) {
        nth[i] = -1;
    }
    cin >> n >> k;
    int cnt = 0;
    q.push(n);
    while (true) {
        cnt++;
        int tmp = q.front();
        visit[tmp] = true;
        nth[n] = 1;
        if (tmp == k) {
            cout << nth[tmp]-1;
            break;
        }
 
        if (tmp - 1 < 0 || visit[tmp-1]) {
        }
        else {
            q.push(tmp - 1);
            visit[tmp - 1] = true;
            if (nth[tmp - 1] == -1) {
                nth[tmp - 1] = nth[tmp] + 1;
            }
        }
 
        if (tmp + 1 > 100000 || visit[tmp+1]) {
        }
        else {
            q.push(tmp + 1);
            visit[tmp + 1] = true;
            if (nth[tmp+1] == -1) {
                nth[tmp + 1] = nth[tmp] + 1;
            }
        }
 
        if (tmp*2 > 100000 || visit[tmp*2]) {
        }
        else {
            q.push(tmp *2);
            visit[tmp*2] = true;
            if (nth[tmp*2] == -1) {
                nth[tmp*2] = nth[tmp] + 1;
            }
        }
 
        q.pop();
    }
 
 
    return 0;
}