[백준] 숨바꼭질 3

문제 개요

오늘의 코딩 테스트 문제는 백준의 "숨바꼭질 3"이다. 수빈이가 동생을 찾아가는 최단 시간을 구하는 문제로, BFS(너비 우선 탐색)의 응용이 필요한 전형적인 그래프 탐색 문제다.

문제 분석

핵심 포인트는 다음과 같다:

수빈이의 이동 방식: X-1, X+1 (1초 소요), 2*X (0초 소요)

목표: 동생의 위치에 도달하는 최소 시간

이 문제의 특이점은 순간이동(2*X)에 시간이 소요되지 않는다는 점이다. 이는 일반적인 BFS로는 최적해를 찾기 어렵게 만든다.

접근 방식

BFS 기반 접근

•

큐를 사용한 기본적인 BFS 구현

•

문제점: 순간이동의 0초 소요를 제대로 반영하지 못함

우선순위 큐를 활용한 개선

•

시간을 기준으로 우선순위 큐 구현

•

이점: 0초 소요 동작을 우선적으로 처리 가능

방문 체크 최적화

•

중복 방문 방지로 불필요한 연산 제거

코드 구현

먼저 기본적인 BFS로 구현했다.

#include <iostream>
#include <queue>

using namespace std;

int N, K;

int main()
{
    cin >> N >> K;

    int cnt = 0;
    
    queue<pair<int, int>> q;
    q.push({N, 0}); // 좌표, 소요시간

    while(!q.empty())
    {
        pair<int,int> n = q.front();
        q.pop();

        if (n.first==K)
        {
            cnt = n.second;
            break;
        }

        if (n.first < 100'000)
            q.push({n.first+1, n.second+1});
        if (n.first > 0)
            q.push({n.first+1, n.second-1});
        if (n.first <= 50'000)
            q.push({n.first*2, n.second});
    }

    cout << cnt << endl;

    return 0;
}
C++
복사

이 접근은 메모리 초과로 실패했다. 큐에 너무 많은 상태가 쌓이는 것이 원인이었다.

다음으로 우선순위 큐와 방문 체크를 도입했다.

#include <iostream>
#include <queue>

using namespace std;

const int MAX_SIZE = 100'000;

int main()
{
    int N, K;
    cin >> N >> K;

    int cnt = 0;
    
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
    vector<bool> visited(MAX_SIZE, false);

    q.push({0, N}); // 소요시간, 좌표
    
    while(!q.empty())
    {
        pair<int,int> n = q.top();
        q.pop();

        if (n.second==K)
        {
            cnt = n.first;
            break;
        }
        
        if (visited[n.second])
            continue;
        visited[n.second] = true;

        if (n.second < 100'000)
            q.push({n.first+1, n.second+1});
        if (n.second > 0)
            q.push({n.first+1, n.second-1});
        if (n.second <= 50'000)
            q.push({n.first, n.second*2});
    }

    cout << cnt << endl;

    return 0;
}
C++
복사

최적화 과정

우선순위 큐 도입

•

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>>

•

시간을 기준으로 정렬하여 최소 시간 우선 처리

방문 체크 배열 사용

•

vector<bool> visited(MAX_SIZE, false)

•

중복 방문 방지로 불필요한 연산 제거

범위 체크 최적화

•

n.second <= 50'000 조건으로 불필요한 연산 방지

회고

이번 문제를 통해 기본적인 BFS만으로는 해결할 수 없는 케이스가 있다는 것을 다시 한번 상기했다. 우선순위 큐의 활용이 이런 특수한 상황에서 얼마나 효과적인지 체감했다.

개선할 점은 초기 접근에서 문제의 특성을 더 꼼꼼히 분석했어야 한다는 것이다. 순간이동의 0초 소요를 간과한 것이 첫 번째 구현의 실패 원인이었다.

다음에는 문제를 읽을 때 이런 특이 케이스를 놓치지 않도록 주의해야겠다. 또한, 그래프 탐색 문제에서 우선순위 큐의 활용을 항상 고려해봐야겠다는 생각이 들었다.