(매일 BOJ) C++ 13549번 숨바꼭질 3

이번 문제는 13549번 숨바꼭질 3이다

문제 요약

• 수빈이는 현재 위치 N, 동생은 위치 K에 있고 수빈이가 이동할 수 있는 방법은 세 가지다
  1. X - 1 (1초 소요)
  2. X + 1 (1초 소요)
  3. X * 2 (0초 소요)

즉, 간선의 가중치가 0 또는 1인 그래프 최단거리 문제인데 일반 BFS로는 가중치 차이를 반영할 수 없기 때문에, 덱을 이용한 0-1 BFS가 필요합니다.

 

덱(deque)

• Double Ended Queue의 줄임말 → “앞뒤 양쪽에서 넣고 뺄 수 있는 큐”
• std::deque 로 C++ STL에서 제공
• 특징:
  • push_front() / pop_front() → 앞에서 삽입·삭제
  • push_back() / pop_back() → 뒤에서 삽입·삭제
• 즉, 스택(stack)과 큐(queue)의 장점을 합쳐 놓은 자료구조

 

덱을 왜 쓰나?

1. 양쪽 삽입/삭제가 모두 O(1) → 빠름
2. 상황에 따라 “앞에서 넣을지, 뒤에서 넣을지” 선택 가능
3. 그래서 0-1 BFS 같은 문제에서 매우 유용
   • 가중치 0 → push_front() (바로 처리)
   • 가중치 1 → push_back() (한 단계 뒤 처리)

 

접근법

• 가중치가 0인 간선 → push_front()
• 가중치가 1인 간선 → push_back()

이렇게 하면 덱의 앞쪽에는 항상 "더 빨리 도달할 수 있는 위치"가 들어오게 되고, 최단 시간이 자연스럽게 보장된다

 

작성코드

#include <bits/stdc++.h>
using namespace std;

int N,K;

int BFS (void);

int main (void){
    cin >> N >> K;
    
    auto a = BFS();

    cout << a;

    return 0;
    
}

int BFS (void){
    vector<int> distance(100001,1000000);
    
    deque<int> dq;
    dq.push_back(N);
    distance[N] = 0;
 
    while(!dq.empty()){
        int x = dq.front();
        dq.pop_front();

        if (x == K) break;

        int nx = x*2;
        if(nx <= 100000 && distance[x] < distance[nx]){
            distance[nx] = distance[x];
            dq.push_front(nx);
        }

        for(int next : {x-1,x+1}){
            if (0 > next || next > 100000) continue;

            if(distance[next] > distance[x] + 1){
                distance[next] = distance[x] + 1;
                dq.push_back(next);
            }
        }
    }
    return distance[K];

}