[Baekjoon(백준)][12851번] 숨바꼭질 2(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "숨바꼭질 2" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제는 수빈이가 동생을 찾기 위해 이동하는 가장 빠른 시간과 그 시간으로 동생을 찾는 방법의 수를 구하는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

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

12851번: 숨바꼭질 2

문제개요

"숨바꼭질 2" 문제는 수빈이가 동생을 찾기 위해 이동하는 가장 빠른 시간과 그 시간으로 동생을 찾는 방법의 수를 구하는 문제입니다. 수빈이는 걷거나 순간이동을 할 수 있으며, 걷는 경우 한 칸 앞이나 뒤로 이동하고, 순간이동을 하는 경우 현재 위치의 2배로 이동합니다.

해결전략

이 문제는 BFS(너비 우선 탐색)를 사용하여 해결할 수 있습니다. 각 위치에서 걷거나 순간이동을 하는 경우의 위치를 큐에 추가하며, 해당 위치까지 도달하는 데 걸린 시간과 그 시간으로 도달하는 방법의 수를 기록합니다. 방문하지 않은 위치를 방문할 때는 큐에 추가하고, 이미 방문한 위치에 도달하는 다른 경로를 찾았을 때 해당 위치까지의 시간이 같으면 방법의 수만 업데이트합니다.

코드 구현

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

int N, K; // 수빈이의 위치 N, 동생의 위치 K
int counts[100002]; // 각 위치까지 도달하는 방법의 수
int visited[100002]; // 각 위치까지 도달하는 데 걸린 최소 시간

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

    cin >> N >> K;
    if (N == K) { // 시작 위치와 동생의 위치가 같은 경우
        cout << "0\n1\n";
        return 0;
    }
    visited[N] = 1; // 수빈이의 위치를 방문 처리
    counts[N] = 1; // 수빈이의 위치로 도달하는 방법은 1가지

    queue<int> q; // BFS를 위한 큐
    q.push(N); // 큐에 수빈이의 위치를 추가
    while (!q.empty()) {
        int cur = q.front(); // 현재 위치
        q.pop();
        for (int next : {cur - 1, cur + 1, cur * 2}) { // 걷거나 순간이동하는 경우의 위치
            if (0 <= next && next <= 100000) { // 범위 내의 위치인 경우
                if (!visited[next]) { // 방문하지 않은 위치인 경우
                    q.push(next); // 큐에 추가
                    visited[next] = visited[cur] + 1; // 시간 업데이트
                    counts[next] += counts[cur]; // 방법의 수 업데이트
                } else if (visited[next] == visited[cur] + 1) { // 이미 방문한 위치지만 최소 시간으로 도달한 경우
                    counts[next] += counts[cur]; // 방법의 수만 업데이트
                }
            }
        }
    }
    cout << visited[K] - 1 << "\n"; // 동생을 찾는 데 걸린 최소 시간 출력
    cout << counts[K] << "\n"; // 방법의 수 출력
}

코드 설명

위 코드는 BFS를 사용하여 수빈이가 동생을 찾는 데 걸리는 최소 시간과 그 방법의 수를 구합니다. 수빈이의 위치를 시작점으로 하여 걷거나 순간이동할 수 있는 모든 위치를 큐에 추가하면서 탐색합니다. 이미 방문한 위치에 대해서는 최소 시간으로 도달했을 때만 방법의 수를 업데이트합니다. 최종적으로 동생의 위치에 도달하는 데 걸린 최소 시간과 방법의 수를 출력합니다.

결론

"숨바꼭질 2" 문제는 BFS 알고리즘을 사용하여 각 위치까지의 최소 시간과 그 시간으로 도달하는 방법의 수를 계산함으로써 해결할 수 있습니다. 이를 통해 주어진 문제의 요구사항을 효과적으로 만족시킬 수 있습니다.