백준[1697] 숨바꼭질

기본적인 BFS문제만 풀다가 살짝 응용한 문제를 마주치니 정말 어렵게 느껴졌다..

 

주의할 점)

-1, +1, *2를 하고 탐색을 할 때 동생의 지점보다 넘어가서 뒤로 되돌아오는 경우가 더 시간이 짧게 걸리는 예제가 존재한다.

 

 

□ 소스 코드

#include <bits/stdc++.h>
#define MAX 100001
#define MIN 0

bool disList[MAX] = {false};
int seekCnt = 0;
int suN, broK;

void hidebfs(){
    queue<pair<int,int>> disQ;
    
    disQ.push(make_pair(suN,0));
    int subin = disQ.front().first;
    int time = disQ.front().second;
    disList[subin] = true;
    
    while(!disQ.empty()){
        subin = disQ.front().first;
        time = disQ.front().second;
        disQ.pop();
        
        if(subin == broK){
            seekCnt = time;
            return;
        }
        
        int beforeLocate = subin - 1;
        int nextLocate = subin + 1;
        int doubleLocate = subin * 2;
       
        if(beforeLocate >= MIN && !disList[beforeLocate]){
            disList[beforeLocate] = true;
            disQ.push(make_pair(beforeLocate,time + 1));
        }
        if(nextLocate <= MAX && !disList[nextLocate]){
            disList[nextLocate] = true;
            disQ.push(make_pair(nextLocate,time + 1));
        }
        if(doubleLocate <= MAX && !disList[doubleLocate]){
                disList[doubleLocate] = true;
                disQ.push(make_pair(doubleLocate,time + 1));
        }
       
        
    }
}

void hideAndSeek(){
    cin>>suN>>broK;
    
    hidebfs();
    cout<< seekCnt << endl;
}