백준 12851번 [숨바꼭질 2](C++)-yes6686- 티스토리

백준 문제 풀이: 12851 [숨바꼭질 2]

---

문제 링크: https://www.acmicpc.net/problem/12851

문제 설명:

수빈이는 현재 위치 n에 있고, 동생은 위치 k에 있습니다. 수빈이는 1초 후에 다음 중 하나의 행동을 할 수 있습니다:

• n - 1로 이동
• n + 1로 이동
• n * 2로 이동

수빈이가 동생을 찾을 수 있는 가장 빠른 시간과 그러한 경우의 수를 출력하는 문제입니다.

입력:

• 첫 번째 줄에 정수 n과 k가 주어집니다. (0 ≤ n, k ≤ 100,000)

출력:

• 첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력합니다.
• 둘째 줄에 가장 빠른 시간으로 동생을 찾는 경우의 수를 출력합니다.

---

문제 해결 코드

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

const int MAX = 100001;
int visited[MAX];  // 방문 시간 저장
int ways[MAX];     // 경로 수 저장

void bfs(int start, int target) {
    queue q;
    q.push(start);
    visited[start] = 0;  // 시작 위치에서 소요 시간은 0
    ways[start] = 1;     // 시작 위치에서의 경우의 수는 1

    while (!q.empty()) {
        int current = q.front();
        q.pop();

        for (int next : {current - 1, current + 1, current * 2}) {
            if (next < 0 || next >= MAX) continue;

            if (visited[next] == -1) { // 처음 방문하는 경우
                visited[next] = visited[current] + 1;
                ways[next] = ways[current];
                q.push(next);
            } else if (visited[next] == visited[current] + 1) { // 같은 시간에 도달한 경우
                ways[next] += ways[current];
            }
        }
    }
}

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

    int n, k;
    cin >> n >> k;

    fill(visited, visited + MAX, -1); // 방문 배열 초기화

    bfs(n, k);

    cout << visited[k] << '\n'; // 최소 시간
    cout << ways[k] << '\n';    // 경우의 수

    return 0;
}

예제

입력:
5 17

출력:
4
2

입력:
0 100

출력:
28
1

---

코드 설명

• BFS 탐색:
  • BFS를 사용해 가장 빠른 시간으로 동생을 찾습니다.
  • visited[next] 배열은 현재 위치에 도달한 최소 시간을 저장합니다.
  • ways[next] 배열은 해당 위치에 도달할 수 있는 경로의 수를 저장합니다.
• 경로 수 갱신:
  • 만약 visited[next]가 현재 위치의 최소 시간보다 1 크다면, 새로운 최단 경로가 발견된 것이므로 경로 수를 갱신합니다.
  • 동일한 최단 시간에 도달한 경우에는 경우의 수를 누적합니다.
• 초기화:
  • visited 배열을 -1로 초기화하여 방문 여부를 확인합니다.

시간 복잡도

• BFS는 각 노드를 한 번씩 방문하므로 시간 복잡도는 O(V + E)입니다.
• 노드의 수가 최대 100,001이므로, 효율적으로 동작합니다.

---

결과

코드는 가장 빠른 시간과 해당 경우의 수를 정확히 계산하며, BFS와 배열을 활용한 최적화로 대규모 입력에도 효율적으로 작동합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!