숨바꼭질 2

배운 부분이 puts();

for (int num : {-1, 1, *2}) 이 문법?

• 경우의 수

일단 "최단거리" 문제이기 때문에 BFS를 사용해야한다.

그래서 이문제는 "경우의 수" + "BFS"이다.

또한 "반례"가 존재한다.

경우의 수는 "더하기" 이다.

검은색 정점으로 가는 총 경우의 수는

"빨간 정점으로 가는 경우의 수" + "주황 간선에서 검은색 정점으로 가는 경우의 수" 이다.

위의 그림같은 경우에는 2가지 경우가 나온다.

cpp코드

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#define endl "\n"
#define ll long long
const int INF = 987654321;
int n, m;
int visited[100004], cnt[100004];
int dx[3] = {-1, 1, 2};

void BFS(int here)
{
    visited[here] = 1;
    cnt[here] = 1;
    queue<int> q;
    q.push(here);
    
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (int next : {x - 1, x + 1, x * 2})
        {
            // Check OverFlow
            if (0 <= next && next <= 100000)
            {
                if (!visited[next])
                {
                    q.push(next);
                    visited[next] = visited[x] + 1;
                    cnt[next] += cnt[x];
                }
                else if (visited[next] == visited[x] + 1)
                {
                    cnt[next] += cnt[x];
                }
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    // counterexample
    if (n == m)
    {
        puts("0"); puts("1");
        return 0;
    }
    
    BFS(n);

    cout << visited[m] - 1 << endl;
    cout << cnt[m] << endl;

    int a = 10;

    return 0;
}