[12851] 숨바꼭질 2

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

12851번: 숨바꼭질 2

<문제>

이 문제의 절반은 [1697]숨바꼭질 문제(https://www.acmicpc.net/problem/1697)와 동일하다. 
해당 문제의 풀이는 여기서 볼 수 있다 : [1697] 숨바꼭질 :: Dizlet-Algorithm (tistory.com)

 

기존의 숨바꼭질 문제에서 추가된것은, 최적해의 개수가 몇개인지를 구하는 부분이다.

기존의 bfs는 새로운 원소를 push하자마자, 혹은 하기 직전에 visit을 체크해주었다면

이문제 같은 경우, 다음 정점을 모두 push한 이후에 visit을 체크해주어야 한다.

그렇지 않으면 모든 리프노드를 탐색하지 않게 되고, 최적해의 개수가 실제보다 적게 나오는 오류가 발생한다.

 

먼저 도착한것이 항상 최적해라는 사실은 변하지 않으므로, 처음으로 도착한 최적해인지를 판별하기 위한

bool형 변수를 하나 만들어서 false인 경우에는 최적해를 업데이트하고 이를 true로 바꿔준다.

true일때에는 최적해가 무엇인지는 탐색이 완료되었으므로 현재의 turn이 최적해와 같은지를 먼저 판별하고

같다면 경로의 개수를 하나 증가시켜준다.

 

바뀐것은 방문체크의 순서가 결정적이며 유일한 차이점이지만 bfs를 잘 이해해야 풀 수 있는 문제로 생각된다.

<소스코드>

#include <limits.h>
#include <stdio.h>
 
#include <algorithm>
#include <queue>
using namespace std;
queue<pair<int, int>> q;
const int INF = INT_MAX;
const int SIZE = 100001;
int n, k;
bool visit[100001];
int main(void) {
    int cur = 0, min_cnt = 0, i, cnt = 0, ans = 1;
    bool find = false;
    scanf("%d %d", &n, &k);
    if (n == k) {
        printf("0\n1");
        return 0;
    }
    q.push(make_pair(n, 0));
    visit[n] = true;
    while (!q.empty()) {
        cur = q.front().first;
        cnt = q.front().second;
        q.pop();
        visit[cur] = true;
        if (find == true && cnt == min_cnt && cur == k) {
            ans++;
        }
        if (cur == k && find == false) {
            find = true;
            min_cnt = cnt;
        }
        if (cur * 2 <= SIZE && !visit[cur * 2]) {
            q.push(make_pair(cur * 2, cnt + 1));
        }
        if (cur + 1 <= SIZE && !visit[cur + 1]) {
            q.push(make_pair(cur + 1, cnt + 1));
        }
        if (cur - 1 >= 0 && !visit[cur - 1]) {
            q.push(make_pair(cur - 1, cnt + 1));
        }
    }
    printf("%d\n%d", min_cnt, ans);
    return 0;
}