[Baekjoon/C++] 13549번 - 숨바꼭질 3

[백준] Baekjoon Online Judge

문제로 이동

 

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

---

풀이

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

#define MAX 100000

bool check[MAX + 1];

void bfs(int start, int end);

void bfs(int start, int end) {
    queue<pair<int, int>> q;

    q.push({ start, 0 });
    check[start] = true;

    while (!q.empty()) {
        int x = q.front().first;
        int time = q.front().second;
        q.pop();

        if (x == end) {
            cout << time << '\n';
            return;
        }

        int nx[3] = { x * 2, x - 1, x + 1 };         // 다음 위치
        int ntime[3] = { time, time + 1, time + 1 }; // 다음 위치에 도달하는데 걸리는 시간

        for (int i = 0; i < 3; i++) {
            if (nx[i] <= MAX && nx[i] >= 0 && !check[nx[i]]) {
                q.push({ nx[i], ntime[i] });
                check[nx[i]] = true;
            }
        }
    }
}

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

    int N, K;
    cin >> N >> K;

    bfs(N, K);

    return 0;
}

너비 우선 탐색 알고리즘으로 문제를 풀었다.

 

void bfs(int start, int end) {
    queue<pair<int, int>> q;

    q.push({ start, 0 });
    check[start] = true;

    while (!q.empty()) {
        int x = q.front().first;
        int time = q.front().second;
        q.pop();

        if (x == end) {
            cout << time << '\n';
            return;
        }

        int nx[3] = { x * 2, x - 1, x + 1 };         // 다음 위치
        int ntime[3] = { time, time + 1, time + 1 }; // 다음 위치에 도달하는데 걸리는 시간

        for (int i = 0; i < 3; i++) {
            if (nx[i] <= MAX && nx[i] >= 0 && !check[nx[i]]) {
                q.push({ nx[i], ntime[i] });
                check[nx[i]] = true;
            }
        }
    }
}

bfs를 하는 함수이다. 다음에 방문할 칸 (*2, -1, +1)이 어떤 칸이든 큐에 push하고, check[]에 표시하는 것은 같다. 그렇기에 코드의 중복을 피하기 위해 다음에 방문할 칸과 그 칸에 도달하는데 걸리는 시간을 미리 계산하였다. 그리고 그 값을 nx[]와 ntime[]에 저장해서 사용하도록 하였다.