[BOJ 12851번/C++] 숨바꼭질 2

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

12851번: 숨바꼭질 2

숨바꼭질 2

풀이

이전에 풀었던 문제인 숨바꼭질 3의 전편(?) 같은 느낌이다.

숨바꼭질 3에서의 순간이동이 0초였다면, 이곳에서는 1초라고 한다.

 

이번에는 BFS를 활용한다.

각 좌표가 노드라고 생각하고, 다음 노드는 각각

X + 1, X - 1, X * 2가 된다.

 

방문 표시를 할 때 유의할 사항이 있다. 원래의 BFS를 생각하면, 큐에 노드를 넣을 때 마다 방문 체크를 해주었다.

그런데, 여기서는 그렇게 진행하면 안 된다. 그 지점까지 가는 다른 방법들이 존재하고, 그 방법들의 수를 구하는 것이 이 문제의 목표이기 때문이다.

 

그러면 방문 체크를 어디서 해야할까?

그것은 바로 pop을 한 이후이다. pop을 한 이후에는 그 지점까지 최단 거리로 이동하는 방법은 존재하지 않는다는 점을 이용하는 것이다.

 

예를 들어, 수빈이는 현재 1의 지점에 있고 동생이 2의 지점에 있다고 하자.

그렇다면 방법은 아래의 2가지가 있다.

1. 1에서 오른쪽으로 한 칸 걷기.

2. 1에서 순간이동하기.

 

이를 BFS에서 일반적으로 처리하는 경우를 보자.

if (!visited[x + 1]) {
    visited[x + 1] = true;
    queue.push(x + 1);
}

if (!visited[x * 2] {
    visited[x * 2] = true;
    queue.push(x * 2);
}

이 경우에는 결과는 1개만 나온다. 왜?

이미 이동하려는 곳은 방문 처리가 되어서 순간이동의 경우를 고려할 수 없기 때문이다.

 

1에서 오른쪽으로 한 칸 걷기 -> 방문 처리

1에서 순간이동하기 -> 이미 방문 처리되어 있어서 방문하지 않음

 

그래서, 방문 처리를 큐의 값을 pop한 이후에 하게 되면 위 문제를 해결할 수 있다.

 

#include <iostream>
#include <queue>

#define endl '\n'

using namespace std;

bool visited[100001];

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    
    int N, K;
    cin >> N >> K;

    queue<pair<int, int>> q;
    q.push({ N, 0 });

    int answer = 0;
    int min_count = 987654321;
    while (!q.empty()) {
        pair<int, int> xc = q.front();
        q.pop();
        int x = xc.first;
        int c = xc.second;
        // 지금 위치까지 오는 다른 최단 경로의 존재 가능성이 있음.
        // 그래서 큐에 푸쉬할 때 방문 설정을 하는 것이 아닌,
        // 큐에서 팝되는 순간에 방문 설정을 함.
        visited[x] = true;

        if (x == K) {
            if (c < min_count) {
                answer = 1;
                min_count = c;
            }
            else if (c == min_count) {
                answer++;
            }
        }
        else {
            if (x + 1 <= 100000 && !visited[x + 1])
                q.push({ x + 1, c + 1 });
            if (x - 1 >= 0 && !visited[x - 1])
                q.push({ x - 1, c + 1 });
            if (x * 2 <= 100000 && !visited[x * 2])
                q.push({ x * 2, c + 1 });
        }
    }

    cout << min_count << endl;
    cout << answer << endl;

    return 0;
}