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

이번 문제는 1697번 숨바꼭질이다

문제 요약

수빈이는 현재 점 N에 있고, 동생은 점 K에 있는데 수빈이는 매 초마다 다음 세 가지 행동 중 하나를 할 수 있다

1. X - 1 로 이동
2. X + 1 로 이동
3. X × 2 로 순간이동

목표는 수빈이가 동생에게 도달하는 최소 시간을 구하는 것
좌표의 범위 = 0 ≤ N, K ≤ 100000

 

아이디어

• 모든 이동의 가중치가 동일(=1초) 이므로 BFS(너비 우선 탐색) 을 적용하면 된다
• BFS는 가까운 곳부터 탐색하기 때문에, 처음으로 K에 도착했을 때의 시간이 곧 최소 시간
• 정점(Vertex): 수빈이가 위치할 수 있는 좌표 (0 ~ 100000)
• 간선(Edge): 한 번의 이동 (X-1, X+1, X*2)

작성코드

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

int N,K;

int BFS (void);

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

    cout << result;
    
}

int BFS (void){
    vector<bool> visited(100001);
    queue<pair<int,int>> q;
    q.push({N,0});

    while(!q.empty()){
        int x = q.front().first;
        int time = q.front().second;
        q.pop();

        if(x == K) return time;

        for(int next : {x-1,x+1,x*2}){
            if(0 <= next && next <= 100000 && !visited[next]){
                visited[next] = true;
                q.push({next, time + 1});
            }
        }
    }

}