BOJ : 1697 숨바꼭질

문제 : https://www.acmicpc.net/problem/1697

github : https://github.com/JEONG-SEUNGWOOK/BOJ/blob/master/1697.cpp

문제 출처

 Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO US Open 2007 Contest > Silver 2번

• PKU Judge Online
• TJU Online Judge

순간이동을 포함한 1차원 탐색문제

방문한 index만 관리해주면 BFS로 간단하게 해결 가능하다.

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

int N, K;
pair<int, int> p;
queue<pair<int, int>> q;
bool isVisited[100005];
int ans;
int main(){
    scanf("%d%d",&N,&K);
    q.push(make_pair(N, 0));
    while(!q.empty()){
        p = q.front(); q.pop();
        int time = p.second;
        int pos = p.first;
        isVisited[pos]=true;
        
        if(pos == K){
            ans=time;
            break;
        }
        if(pos*2<=100000 && !isVisited[pos*2] ) q.push(make_pair(pos*2, time+1));       
        
        if(!isVisited[pos-1] && pos-1 >= 0)
            q.push(make_pair(pos-1, time+1));       
       
        if(!isVisited[pos+1] && pos+1 <= 100000) q.push(make_pair(pos+1, time+1));        
    }
    cout<<ans<<'\n';
}