문제

문제 링크

해설

• 수빈이가 이동할 수 있는 경우의 수는 좌표 x를 기준으로 {x - 1 , x + 1, x * 2} 3가지 입니다.
• 또한, 동생을 찾기 위한 최단거리를 찾아야 하므로 BFS를 사용해야 함을 알 수 있습니다.
• 즉, 일반적으로 2차원 배열 상에서 이뤄지던 DFS/BFS 문제의 상, 하, 좌, 우 4방향이 3가지 방향으로 바뀌었을 뿐입니다.
• 동생의 위치 K에 도달했을 때
  • BFS 특성에 따라 K에 처음 도달했을 때 (K가 아직 초깃값을 가지고 있을 때) 가장 빠르게 도착했음을 보장할 수 있고,
  • 다음으로 K에 도달한 경우의 수가 있을 때, 이때 같은 time에 도착했다는 정보를 갖고 있다면, 해당 경우의 수를 ‘K에 가장 빠르게 도달하는 또 하나의 경우의 수’로 볼 수 있습니다.
• Queue의 내용물이 빌 때까지 BFS를 수행한 뒤 결과를 출력하면 됩니다.

주의

• 수빈이가 ‘처음에 존재할 수 있는 범위’는 분명 [0, 100000]이 맞습니다.
• 하지만, 동생에게 가는 최단거리를 가는 과정에서 좌표 10만을 넘을 수 있다는 점을 눈치채야 합니다.
  • 이 점을 고려하셨다면 정말 눈치가 대단하신겁니다. 왜냐하면, 문제에는 명시돼있지 않지만 분명히 한 번은 고려해야봐야 하는 조건이기 때문입니다.
  • 예를 들어 단순히 +1로 정방향으로 가는 것보다, 2배를 해 10만 이상 좌표에서 역방향으로 진행하는 게 더 빠를 수 있습니다.
• 다행인지 불행인지, 이번 문제에서는 이것을 고려하지 않아도 AC를 받을 수 있습니다.
• 왜냐하면, 순간이동 해 역방향으로 진행하는 것은 역방향으로 진행한 뒤 순간이동하는 것과 같기 때문입니다.
• 따라서 수빈이가 좌표 10만을 넘는 일은 고려하지 않아도 됩니다.

코드

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

int N, K, t[100'001];

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> N >> K;

    int answer_time = 1e9, answer_method = 0;

    queue<pair<int, int>> q;
    q.emplace(N, 0);
    fill(t, t + 100'001, 1e9);
    t[N] = 0;
    while (!q.empty()) {
        int here = q.front().first, now = q.front().second;
        q.pop();
        if (now > answer_time) continue;
        if (here == K) {
            answer_time = min(answer_time, now);
            if (answer_time == now) answer_method++;
            continue;
        }
        for (int there : {here * 2, here + 1, here - 1}) {
            if (0 <= there && there <= 100'000 && now + 1 <= t[there]) {
                q.emplace(there, now + 1);
                t[there] = now + 1;
            }
        }
    }
    cout << answer_time << '\n' << answer_method << '\n';
    return 0;
}

• fill() 함수를 사용해 초깃값을 임의의 큰 수 1e9로 초기화 한 뒤 BFS를 수행합니다.
• Queue에는 '현재 좌표'와 '현재 수행시간'을 기록합니다.
• 좌표 K(동생 위치)에 도달했을 때, '현재 수행시간'이 최단 수행시간과 동일하다면, 정답을 찾는 다른 방법이므로 카운팅합니다.

소스코드 링크

결과