12851 숨바꼭질 2 -BFS

1. 문제

2. 코드

#include <stdio.h>
#include <queue>
#include <iostream>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
 
const int MAX = 100001;
 
bool visit[MAX];
 
int cnt;
int ans;
 
int main()
{
    int N, K;
    scanf("%d %d", &N, &K);
    queue<pair<int,int>> q;
    
    q.push(make_pair(N,0));
    visit[N] = true;
 
    while (!q.empty())
    {    
        int cur = q.front().first;
        int curSec = q.front().second;
        q.pop();
 
        visit[cur] = true;
            
        if (ans && ans == curSec && cur == K) {
            cnt++;
        }
 
 
        if (!ans && cur == K) {
            ans = curSec;
            cnt++;
        }
 
        if (cur + 1 < MAX && !visit[cur+1])
            q.push(make_pair(cur+1, curSec +1));
        if (cur - 1 >= 0 && !visit[cur-1])
            q.push(make_pair(cur - 1, curSec + 1));
        if (cur * 2 < MAX && !visit[cur*2])
            q.push(make_pair(cur * 2, curSec + 1));
    }
    printf("%d\n", ans);
    printf("%d\n", cnt);
}
 

3. 후기

1 7 의 경우 경로는 총 네 가지이다. 

1 2(+1) 3 6 7

1 2(+1) 4 8 7

1 2(*2) 3 6 7

1 2(*2) 4 8 7