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

문제

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

백준 1697

 

문제 내용

수빈이가 동생이 있는 곳까지 가장 빠르게 갈 수 있는 시간을 구하면 된다. 

수빈이는 1초 후에 x-1, x+1, 2x 의 위치로 이동할 수 있다.

 

문제 풀이

bfs를 통해 문제를 풀면 된다.

while문을 돌면서 배열에 방문했다는 표시를 true/fasle로 남기는 것이 아니라, 그 위치까지 몇 초 걸리는지를 남기면 된다.

 

코드

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

int arr[100001];
int n, k;

int returnNextPosition(int type, int num) {
    if (type == 0)
        return num - 1;
    else if (type == 1)
        return num + 1;
    else
        return num * 2;
}

int bfs(int n, int k) {
    queue<int> q;

    q.push(n);
    arr[n] = 1;

    while (!q.empty()) {
        int idx = q.front();
        q.pop();

        for (int i = 0; i < 3; i++) {

            int next = returnNextPosition(i, idx);

            // 인덱스 체크 && 아직 방문 안 했을 경우
            if (next >= 0 && next <= 100000 && arr[next] == 0) {
                q.push(next);
                arr[next] = arr[idx] + 1;
            }
        }
    }

    return arr[k] - 1; // 처음 시작할 때 1초로 두고 했기 때문에 -1 필요
}

int main() {
    cin >> n >> k;

    cout << bfs(n, k);
}