숨바꼭질 2 12851

문제

접근 방법

특정수까지 도착할 때 최소 비용, 해당하는 방법의 개수를 묻는 문제이다.
최소 비용만을 저장하려면 어떻게 해야 할까?

당연한 이야기지만 BFS를 통해 가장 먼저 닿는 곳은 최소 비용이라 할 수 있다. 같은 비용으로 도착하는 것들은 최소 비용으로 가는 길이라고 할 수 있다.

같은 비용으로 도착하였고 위치가 K가 아니면 계속해서 탐색해야 한다. 하지만 위치가 K이면 더 이상 탐색할 필요가 없다. 비용만 늘어날 것이기 때문이다.
이러한 점을 활용하여서 풀면 된다.

하지만 당연하게도 N이 K일 수도 있기에 N이 K인 경우에는 바로 반환해주면 된다.

코드

#include <iostream>
#include <queue>
using namespace std;
int map[100001], ret = 0, N, K;
queue<pair<int, int>> bfs;
void push(int num, int cost)
{
    if (num < 0 || num > 100000)
        return;
    if (!map[num])
        map[num] = cost;
    if (map[num] == cost)
    {
        if (num == K)
            ++ret;
        else
            bfs.push({num, cost});
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> K;
    if (N == K)
    {
        cout << 0 << "\n"
             << 1;
        return 0;
    }
    bfs.push({N, 0});
    while (!bfs.empty())
    {
        pair<int, int> cur = bfs.front();
        bfs.pop();
        int n1, n2, n3, cost = cur.second + 1;
        n1 = cur.first + 1;
        n2 = cur.first - 1;
        n3 = cur.first << 1;
        push(n1, cost);
        push(n2, cost);
        push(n3, cost);
    }
    cout << map[K] << "\n"
         << ret;
    return 0;
}

풀이

1만큼 증감하는 값, 2배가 되는 값을 BFS를 활용하여서 탐색해주면 된다.
만약 도착한 지점의 값이 0이면 아직 도착한 적이 없는 것이기에 갱신해주면 된다.
이후 도착한 지점의 값이 내 비용과 같다면 최소 비용으로 도착한 것이기에 탐색을 계속해준다.

BFS의 특성인 최소 비용을 활용한 문제라고 생각한다.

실수로 N이 K인 경우에 return을 빠트려서 출력이 겹쳤다. 그래서 틀렸다. 잘해두고 틀려서 아쉽다.