백준 12851 (C++) 숨바꼭질

12851번: 숨바꼭질 2

해결

BFS 로 해결했다.

 

숨바꼭질 1 과 다른 점은, queue에 넣기전 방문체크하지 않는다는 것이다.

 

물론 숨바꼭질 1도 queue에 넣은 후 pop하고 나서 방문체크해도 옳은 답이 나온다.

어차피 현재 위치가 동생 위치 k일 때,

bfs탐색을 거쳤으므로 제일 처음 종료조건 k에 도달한 상태가 최적의 답(최소시간)이기 때문이고,

바로 return하기 때문에 방문체크 순서는 상관없기 때문에 그런 것이다.

 

단지 queue에 넣기 전 방문체크 하는 것이 불필요하게 q에 넣는 것을 줄일 수 있기 때문에 그렇게 하는 것이다.

그러나 숨바꼭질 2에서는 queue에 넣기 전 방문체크를 하면, 동일한 위치에는 다시 방문하지 않게 되므로

1→ 1 +1 → 2
2 1 → 12 → 2*2

인 두가지의 과정을 셀 수 없다.

 

현재 코드에서 x-1, x+1, x*2순으로 bfs를 진행하는데,

q에 넣기 전 1 → 1 +1에 대해서 방문체크 할 경우, 1*2의 경로는 셀 수 없기 때문이다.

 

따라서 최소 시간이 걸리는 가짓수를 찾기 위해 queue에 넣고 나서 해당 칸에서 한 칸 진보하는 경우를 모두 queue에 넣는 반복문이 지난 후 pop할 때 방문체크를 해주었다.

코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

const int MAX = 100001;
int n, k;
bool visited[MAX];

pair<int, int> bfs(int first_x, int first_time) {
    fill(visited, visited + MAX, false);
    queue<pair<int, int>> q;
    q.push({first_x, first_time});
    visited[first_x] = true;
    int cnt = 0, min_time = 0;

    while (!q.empty()) {
        int x = q.front().first;
        int time = q.front().second;
        q.pop();
        visited[x] = true;
        if (x == k) {
            if (cnt == 0) { // 처음으로 목표 위치에 도달
                cnt++;
                min_time = time;
            } else if (cnt > 0 && time == min_time) { // 처음 이후 도달이자, 최소 시간인경우
                cnt++;
            }
        }
        if (x > 0 && !visited[x - 1]) {
            q.push({x - 1, time + 1});
        }
        if (x < MAX && !visited[x + 1]) {
            q.push({x + 1, time + 1});
        }
        if (x * 2 < MAX && !visited[x * 2]) {
            q.push({2 * x, time + 1});
        }
    }
    return make_pair(min_time, cnt);
}

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

    cin >> n >> k;
    auto ans = bfs(n, 0);
    cout << ans.first << '\\n' << ans.second;
    return 0;
}