[C/C++] 백준 #1697 숨바꼭질(너비 우선 탐색)

이번 문제는 너비 우선 탐색을 이용해서 풀었습니다.

 

너비 우선 탐색(BFS) 아닌 방법으로도 풀 수 있을 듯 합니다만, 당장 좋은 방법은 떠오르지 않습니다.

 

그래프 탐색 이론을 배울 때, 너비 우선 탐색은 후에 나오는 프림 알고리즘, 다익스트라 알고리즘, A* 알고리즘의 근간이 됩니다.

너비 우선 탐색은 큐(Queue)를 사용하는데, 후에 나오는 알고리즘들은 우선 순위 큐(Priority Queue)를 사용한다는 점이 다릅니다.

 

사실 간선의 가중치 값이 1인 그래프를 생각한다면, 다익스트라 알고리즘을 사용할 수 있지만, 굳이 그럴 이유가 없는 것이 먼저 방문한 것들이 모두 후에 방문한 것들보다 작거나 같은 노드값을 가지고 있기 때문에 우선순위 큐를 사용할 하등의 이유가 없습니다.

 

Hide and Seek

 

제가 작성한 소스입니다.  소스는 참고용으로만 봐주세요.

//----------------------------------------------------------
//    baekjoon #1697
//        - by Aubrey Choi
//        - created at 2019-06-03
//----------------------------------------------------------
#include <stdio.h>
#include <memory.h>

int main()
{
    int n, m, step = 0, queue[100100], sp = 0, ep = 0;
    int v[100100];
    scanf("%d%d", &n, &m);
    if(n >= m)
    {
        printf("%d\n", n - m);
        return 0;
    }
    memset(v, -1, sizeof(v));
    queue[ep++] = n;
    v[n] = step;
    for(; ;)
    {
        int n = queue[sp++];
        step = v[n];
        if(n == m) break;
        if(n + 1 <= 100000 && v[n + 1] == -1)
        {
            queue[ep++] = n + 1;
            v[n + 1] = step + 1;
        }
        if(n - 1 >= 0 && v[n - 1] == -1)
        {
            queue[ep++] = n - 1;
            v[n - 1] = step + 1;
        }
        if(n * 2 <= 100000 && v[n * 2] == -1)
        {
            queue[ep++] = n * 2;
            v[n * 2] = step + 1;
        }
    }
    printf("%d\n", step);
    return 0;
}