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

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

1697번: 숨바꼭질

 

 

문제풀이

 

일차원 선 위에서 BFS를 이용하여 최단거리를 구하였다.

 

이때 수빈이와 동생의 위치는 0부터 100, 000까지이지만

수빈이는 현재 거리의 2배를 순간 이동할 수 있기 때문에 거리 배열을 100,000의 두배인 200,001로 선언하였다.

 

 

코드

#include <iostream>
#include <queue>

using namespace std;

int dist[200001];

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);

    int n,k;
    cin>>n>>k;

    queue<int> q;
    q.push(n); //수빈이의 시작위치
    dist[n] = 1;

    while(true){
        int cur = q.front();
        q.pop();

        if(cur == k){
            cout<<dist[cur]-1; //수빈이의 시작위치가 1이였기 때문에 1을 빼준다.
            return 0;
        }

        if(cur-1 >= 0 && cur-1 <= 200000 && dist[cur-1] == 0){ //-1만큼 걸을때
            dist[cur-1] = dist[cur] + 1;
            q.push(cur-1);
        }

        if(cur+1 >= 0 && cur+1 <= 200000 && dist[cur+1] == 0){ //1만큼 걸을때
            dist[cur+1] = dist[cur] + 1;
            q.push(cur+1);
        }

        if(cur*2 >= 0 && cur*2 <= 200000 && dist[cur*2] == 0){ //*2 순간이동할때
            dist[cur*2] = dist[cur] + 1;
            q.push(cur*2);
        }
    }
}

 

 

결과