[백준] 12851 - 숨바꼭질2

12851. 숨바꼭질 2 풀이

난이도: Gold IV
문제 주소: https://www.acmicpc.net/problem/12851

문제 풀이

이 문제는 수빈이가 동생을 찾는 가장 빠른 시간과 그 방법의 수를 구하는 BFS 문제이지만 기존의 단일 최단 경로 찾기처럼 풀면 문제가 발생할 수 있는 문제이다. 처음에는 다음 구조로 코드를 작성했다.

 

for (int next : next_pos) {
    if (next >= 0 && next <= 200000) {
        if (next == k) {
            int next_time = p.second + 1;
                if (anw.first > next_time) {
                    anw = {next_time, 1};
                } else if (anw.first == next_time) {
                    anw.second++;
                }
    } 
        else if (!visited[next]) {
            visited[next] = true;
            q.push({next, p.second + 1});
        }
    }
}

이런 구조로 큐에 넣을 때 방문 처리를 하도록 문제를 풀게되면 시간 복잡도는 문제가 없고 최단 시간은 구할 수 있을지 몰라도 가장 빠른 시간으로 찾는 방법의 수를 제대로 구할 수 없다. 이렇게 풀게 되면 이미 한 번 큐에 담은 위치는 무조건 방문 처리가 되어버려서, 다른 경로를 통해 같은 시간에 동일한 위치에 도달할 수 있는 경우를 아예 차단하는 문제가 발생한다. 이 문제점을 발견하고는 다음 풀이로 변경을했다.

 

while (s--) {
    int p = q.front();
    q.pop();
    visited[p] = true; 
    
    if (p == k) cnt++;

    int next_pos[3] = {p - 1, p + 1, p * 2};
    for (int next : next_pos) {
        if (next >= 0 && next <= 100000 && !visited[next]) {
            q.push(next);
        }
    }
    if (cnt != 0) break; 
    time++;
}

이번에는 큐에서 꺼낼 때 방문 처리를 하닌까 안일하게 중복 경로가 탐색되어 방법의 수가 해결 될거라 생각했고 이번에도 예제를 통과했으니 풀릴줄 알았지만 여전히 불필요한 탐색을 제어하지 못하는 구조를 벗어나지 못하고 있었다.

 

큐에서 꺼낼 때 방문 처리를 하더라도 최단 시간을 찾았을 때 더 이상의 탐색을 막아주는 브레이크 조건이 정밀하지 않으면 불필요한 경로까지 큐에 계속 들어가게 된다. 예를 들어 N=5, K=17일 때 최단 시간은 4초이고 방법의 수는 2가지이다. 하지만 위 코드처럼 시간을 엄격하게 제어하지 않으면 5에서 파생된 여러 경로들이 17에 도달한 뒤에도 큐에 쌓인 나머지 값들이 계속해서 탐색을 이어나가 메모리 초과나 시간 초과를 유발하게 된다.

 

이 문제를 해결 할려면 루프 안의 방문 처리와 탈출 조건을 다음과 같이 수정해야 한다.

방문 처리를 큐에서 꺼낼 때 하되 동생을 찾았을 때의 최단 시간을 기록해두고 큐에서 꺼낸 현재 시간이 그 최단 시간보다 클 경우 더 이상 탐색하지 않고 루프를 탈출하도록 만들어야 한다.

이렇게 큐에서 꺼낼 때 방문 처리를 하면 같은 시간에 동일한 위치에 도달하는 여러 경로들이 모두 큐에 들어갈 수 있게 되어 방법의 수를 정확히 셀 수 있음을 보장할 수 있게 된다.

 

위에서 사용했던 예시를 떠올려보면 특정 지점에 도달하는 여러 갈래길이 있더라도 방문 처리가 늦게 이루어지기 때문에 중복 경로 카운트가 가능하고 최단 시간 초과 시에는 즉시 탐색을 종료하여 자원 낭비를 막게 된다.

 

예전에도 BFS 문제를 많이 풀었지만 응용이 들어가서 그런가 큐의 상태 관리와 방문 처리 시점을 어떻게 조율해야 했었는지 완전히 까먹었던거 같다....
한두번 수정한걸로 해결이 안돼닌까 점점 멘탈이 나가서 코드 제대로 검토도 안하고 제출을 난사해서 6번 제출 끝에 겨우겨우 풀었다

최단 시간뿐만 아니라 방법의 수까지 구해야 할 때는 큐에 넣을 때가 아니라 꺼낼 때 방문 처리를 해야 중복 경로를 허용할 수 있음을 기억하자...

최종 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <queue>
#include <string>
#include <unordered_map>

using namespace std;
bool visited[100001];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    queue <int> q;
    q.push(n);

    int cnt = 0;
    int time = 0;
    while(!q.empty()) {
        int s = q.size();

        while (s--) {
            int p = q.front();
            q.pop();
            visited[p] = true; 
            
            if (p == k) cnt++;

            int next_pos[3] = {p - 1, p + 1, p * 2};
            for (int next : next_pos) {
                if (next >= 0 && next <= 100000 && !visited[next]) {
                    q.push(next);
                }
            }
        }
        if (cnt != 0) break; 
        time++;
    }
    cout << time << "\n" << cnt;
    return 0;
}

---

'Algorithm > 백준' 카테고리의 다른 글

[백준] 10942 - 팰린드롬?  (0)	2026.03.23
[백준] 2166 - 다각형의 면적 풀이  (0)	2026.03.22
[백준] 12865 - 평범한 배낭  (0)	2026.03.17
[백준] 11053 - 가장 긴 증가하는 부분 수열  (0)	2026.03.13
[백준] 1654 - 랜선 자르기  (0)	2026.03.13