[백준] 1697번 숨바꼭질 (C++)

출처

USACO US Open 2007 Contest Silver 2번

문제 주소

백준 1697번 숨바꼭질

1697번: 숨바꼭질

알고리즘

BFS

힌트

check 배열(방문 배열)에 그곳에 가게 되는 시간 + 1을 저장한다.

 

 

풀이

수빈이가 이동할 수 있는 위치는 3군데가 있다. 각 각의 위치가 주어진 범위를 벗어나지 않는 지 확인을 한 후 왔던 곳인지 확인을 한다. 처음 위치를 1로 하고 (이는 check배열의 본질을 잃지 않기 위함이다.) check[다음위치]에 check[현재위치]+1을 저장해준다. 현재 위치가 목표 위치와 같게 되면 check[현재위치]-1가 답이 된다.

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

int check[100001];
queue<int> q;

int main(){
    int a,b,ans=0;
    cin>>a>>b;
    q.push(a);
    check[a]=1;

    while(!q.empty()){
        int tmp=q.front();
        q.pop();
        if(tmp==b){
            cout<<check[tmp]-1;
            break;
        }
        if(tmp+1<=100000&&!check[tmp+1]){
            q.push(tmp+1);
            check[tmp+1]=check[tmp]+1;
        }

        if(tmp-1>=0&&!check[tmp-1]){
            q.push(tmp-1);
            check[tmp-1]=check[tmp]+1;
        }

        if(tmp*2<=100000&&!check[tmp*2]){
            q.push(tmp*2);
            check[tmp*2]=check[tmp]+1;
        }    

    }
}

백준 1697번 숨바꼭질