12851번

12851번 - 숨바꼭질2

처음에 나는 탐색하는 모든 정점을 큐에 계속 넣고, 답을 찾고, 답보다 깊은 곳에 도달하면 나와서 출력하도록 했다.

근데 이는 예상대로 너무 많은 정점이 큐에 들어가고, 메모리 초과가 발생했다.

그래서 다른 사람들 풀이를 보니까, 큐에서 pop 될때 방문 체크를 하면 된다고 했다.. 이해가 안갔다.. 왜 그런지는 설명이 없었다.

그래서 계속해서 생각해보다가, 

pop 될때 방문체크를 하면, 중복해서 큐에 들어갈 수 있고, 높이가 같은 것들은 모두 집어넣을 수있다.

다른 의문점 하나는, 혹시나 이미 체크된 정점에서 정답값이 나올 수 있지 않겠느냐였다.

하지만 이미 체크된 정점에서 나오는 값에서 정답이 나온다면, 무조건 깊이가 깊어지는 것이 분명하다.

예를 들어 1이라는 루트 노드에서 시작해서 깊이가 3일 때 정답 10이 나왔다고 한다면,

만약 깊이가 2에서 1이라는 값이 다시 나온다고 해도 결국은 깊이 2 + 깊이 3을 더한 깊이 5에서 정답 10이 나올 것이고,

그렇게 된다면 결국 체크할 필요가 없는 답이 되기 때문이다.

이를 통해서 탐색 중인 BFS의 깊이를 계산하면서 구할 수 있었다.

##내가 배운점##

내가 지금 까지 쓴 BFS에서는 탐색 중인 깊이를 알 수가 없었다. 근데 다른 사람들 코드를 보니,

size 와 depth 변수, 그리고 for문을 이용해서 탐색중인 곳의 깊이를 알 수가 있었다.

유용하게 쓸 수 있을 것 같다.

<정답 코드>

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
int dx[3] = { -1,1,2 };
vector<bool> dist(100001, false);
vector<long long> num(100001, 0);
long long cnt;
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
 
    if (n == k)
    {
        printf("0\n1\n");
        return 0;
    }
        
    queue<pair<int,int>> q;
 
    q.push({ n,1 });
 
    int minn = 987654321;
    int size;
    int depth = -1;
 
    while (!q.empty())
    {
        size = q.size();
        depth++;
 
        for (int t = 0; t < size; t++)
        {
            int now = q.front().first;
            q.pop();
 
            dist[now] = true;
 
            if (depth==minn)
            {
                while (!q.empty())
                    q.pop();
                break;
            }
 
            for (int i = 0; i < 3; i++)
            {
                int next;
                if (i == 2)
                {
                    next = now*dx[i];
                }
                else
                {
                    next = now + dx[i];
                }
 
                if (next >= 0 && next <= 100000 && dist[next]==false)
                {
                    if (next == k)
                    {
                        minn = min(minn, depth+1);
                    }
                    q.push({ next,num[next]++ });
                }
            }
        }
    }
 
    printf("%d\n%lld\n", minn,num[k]);
 
    return 0;
}