백준 1697번, 숨바꼭질

백준 1697번 c++ 문제풀이

문제:

백준 1697

풀이:

1. 수빈이와 동생의 위치 n, k를 입력받는다.
2. 수빈이가 동생보다 앞에 있다면, 즉 n이 k보다 크다면, x*2, x+1로는 뒤로 갈수 없으므로
   즉 -1로만 좌표 이동이 가능하다. (n>=k)일 때는 결과값이 n-k이다.
3. 반대로 수빈이가 동생보다 뒤에 있다면, 모든 방법으로 이동이 가능하다. 이 때, bfs를 이용한다.
4. 큐에 처음 위치 n과 0(부모 노드 위치)를 pair로 저장한다. visited[n] = true로 해준다.
5. 큐에서 pop을 하고 그 값으로 부터 갈수 있는 세가지 길에 대해 구한 후, visited = false면 그 값들을 큐에 저장한다. 노드 위치값은 1증가해준다.
6. 찾고자하는 동생의 위치에 도달하면, 노드 위치값을 출력한다.

코드:

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

bool visited[200001];

void bfs(int n, int k) {
    bool fin = false;
    queue<pair<int,int>> q;
    int num = 0;
    q.push({n, num});
    visited[n] = true;

    while(fin == false){
        int p = q.front().first; //위치
        int z = q.front().second;//몇번째 층인지
        q.pop();
        visited[p] = true;
        for(int i=0;i<3;i++){
            int a; //위치 이동값 저장
            if(i==0){
                a = p -1;
            }else if( i == 1){
                a = 2*p;
            }else if( i == 2){
                a = p+1;
            }

            if(a <=200001 && a>=0 && visited[a] == false){
                q.push({a, z+1});
            }
            if(a == k){
                fin = true;
                cout << z+1;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

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

    if(n>=k){
        cout << n-k; //어차피 -1밖에 못함
        return 0;
    }
    else if(n<k){
        bfs(n, k);
    }

    return 0;
}

bfs를 어떻게 적용하는지에 대한 고민이 오래걸렸던 문제였던 것 같다.

감사합니다.