백준 1697 숨바꼭질

<링크>

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

<소스코드>

#include<stdio.h>
#include<queue>
using namespace std;
void check(int);
int bfs();
queue<int> q;
int N, K;
int isVisited[100001];
int main()
{
    scanf("%d%d", &N, &K);
    printf("%d", bfs());
}
int bfs()
{
    q.push(N);
    int depth = 0;
    while (!q.empty())
    {
        int s = q.size();
        for (int i = 0; i < s; ++i)
        {
            int cur = q.front();
            q.pop();
            if (cur == K)
                return depth;
            check(cur+1);
            check(cur-1);
            check(cur*2);
        }
        ++depth;
    }
}
void check(int to)
{
    if (to >= 0 && to <= 100000 && !isVisited[to])
    {
        isVisited[to] = 1;
        q.push(to);
    }
 
}

<풀이>

현재 위치에서부터 BFS를 한다.

1. 한번 봤던 노드는 다시 보지않는다.

5라는 좌표는는 이미 봤던 좌표이고 5까지 가는 거리는 0이다. 나중에 4에서 +1을통해 5로 가던, 6에서 -1을 통해 5로 가던 어떤방식으로든 0보다는 작을 수 없다. 즉, 한 번 방문했던 좌표를 또 방문하는 건 삥 돌아오는 것이라는 뜻이다. 따라서 bfs가지를 뻗어나갈 때 방문했던 노드는 제외시켜버린다.

2. 1의 규칙 때문에 큐에 어떤 숫자가 들어왔다는 것은 그 숫자는 처음 나온 것이라는 말과 같다. 따라서 해당 숫자까지의 depth가 최단거리이다. 목표좌표가 뜨면 그 순간의 depth가 답이 된다.

3. 기존의 bfs방식인 while(!q.empty()) 만으로는 depth를 알 수 없다. 그냥 발견하면 끝이기 때문이다.

그렇기 때문에 while 안에서 현재의 큐 size를 얻어내고, 그만큼 for문을 돌리면 하나의 for문이 곧 한 depth가 된다.

depth를 재는 방식은 다른 방법도있지만 개인적으로 이게 제일 편한것같다.