[백준] 1697 숨바꼭질

문제 설명

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

1697번: 숨바꼭질

수빈이는 점 N(0 <= N <= 100000)에 있고, 동생은 점 K(0 <= k <= 100000)에 있을 때, 수빈이는 1초 후에 x - 1, x + 1, x * 2의 위치로 이동할 수 있다

동생이 있는 위치로 이동하는 가장 빠른 시간을 구하기

 

문제 풀이법

최단거리를 찾는 문제이므로 BFS를 사용하여 풀 수 있다

그동안 했던 BFS는 2차원 배열이며 따라서 상하좌우로만 이동했었는데, 이 문제는 1차원이고 x - 1, x + 1, x * 2의 위치로만 이동할 수 있다는 것만 유념하면 쉽게 풀 수 있던 문제였다

 

배열 arr의 값을 모두 -1로 초기화해 준 후, 큐에 수빈이의 현재위치를 담고 arr[n] = 0으로 셋팅 후, BFS를 돌리면 된다

 

 

소스 코드

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    int n, k;
    int arr[100001];
    
    cin >> n >> k;
    
    queue<int> q;
    
    fill(arr, arr + 100001, -1);
    
    q.push(n);
    arr[n] = 0;
    
    while (arr[k] == -1)
    {
        int x = q.front();
        
        q.pop();
        for (int nx : {x - 1, x + 1, 2 * x})
        {
            if (nx < 0 || nx > 100000)
                continue;
            if (arr[nx] != -1)
                continue;
            arr[nx] = arr[x] + 1;
            q.push(nx);
        }
    }
    
    cout << arr[k];
    
    return 0;
}