[백준 13549] 숨바꼭질 3 (C#, C++) - soo:bak

문제 링크

13549번 - 숨바꼭질 3

설명

수직선 위에서 수빈이와 동생의 초기 위치 N과 K (0 ≤ N, K ≤ 100,000)가 주어지는 상황에서, 수빈이가 위치 X에 있을 때 X-1 또는 X+1로 이동하면 1초가 걸리고, 2×X로 순간이동하면 0초가 걸린다면, 동생을 찾는 가장 빠른 시간을 구하는 문제입니다.

접근법

이동 방법에 따라 시간이 다르므로, 각 이동을 간선으로 보면 가중치가 0 또는 1인 그래프 문제가 됩니다.

일반적인 BFS는 모든 간선의 가중치가 같을 때만 최단 거리를 보장하지만, 가중치가 0과 1만 있는 경우에는 0-1 BFS라는 특별한 방법을 사용할 수 있습니다.

0-1 BFS의 핵심은 덱(deque)을 사용하여 가중치 0인 간선으로 이동할 때는 덱의 앞에, 가중치 1인 간선으로 이동할 때는 덱의 뒤에 넣는 것입니다.

이렇게 하면 덱의 앞쪽에는 항상 현재까지 가장 적은 시간으로 도달할 수 있는 위치가 오게 되어, 각 위치를 최소 시간으로 방문하게 됩니다.

구체적으로, 현재 위치 X에서:

• 순간이동(2×X): 시간이 증가하지 않으므로 덱의 앞에 추가
• 걷기(X-1, X+1): 시간이 1초 증가하므로 덱의 뒤에 추가

예를 들어, 수빈이가 5에 있고 동생이 17에 있다면:

• 5 → 10 (×2, 0초) → 9 (-1, 1초) → 18 (×2, 1초) → 17 (-1, 2초)로 2초에 도달
• 또는 5 → 4 (-1, 1초) → 8 (×2, 1초) → 16 (×2, 1초) → 17 (+1, 2초)로 2초에 도달

이처럼 순간이동을 적극 활용하면 일반 BFS보다 빠른 경로를 찾을 수 있습니다.

각 위치에 대해 현재까지 알려진 최소 시간을 기록하고, 더 빠른 시간으로 도달할 수 있을 때만 갱신하며 탐색을 진행합니다.

목적지에 도달하면 그때의 시간이 최소 시간입니다.

관련 문제: [백준 12851] 숨바꼭질 2 (C#, C++) - soo:bak

관련 문제: [백준 13913] 숨바꼭질 4 (C#, C++) - soo:bak

---

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  class Program {
    const int MAX = 100000;

    static void Main(string[] args) {
      var input = Console.ReadLine()!.Split();
      var n = int.Parse(input[0]);
      var k = int.Parse(input[1]);

      var dist = new int[MAX + 1];
      for (var i = 0; i <= MAX; i++) dist[i] = int.MaxValue;

      var dq = new LinkedList<int>();
      dist[n] = 0;
      dq.AddFirst(n);

      while (dq.Count > 0) {
        var cur = dq.First!.Value;
        dq.RemoveFirst();
        if (cur == k) break;

        var next = cur * 2;
        if (next <= MAX && dist[next] > dist[cur]) {
          dist[next] = dist[cur];
          dq.AddFirst(next);
        }

        next = cur - 1;
        if (next >= 0 && dist[next] > dist[cur] + 1) {
          dist[next] = dist[cur] + 1;
          dq.AddLast(next);
        }

        next = cur + 1;
        if (next <= MAX && dist[next] > dist[cur] + 1) {
          dist[next] = dist[cur] + 1;
          dq.AddLast(next);
        }
      }

      Console.WriteLine(dist[k]);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef deque<int> di;

const int MAX = 100000;

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

  int n, k; cin >> n >> k;
  vi dist(MAX + 1, INT_MAX);
  di dq;
  dist[n] = 0;
  dq.push_front(n);

  while (!dq.empty()) {
    int cur = dq.front();
    dq.pop_front();
    if (cur == k) break;

    int next = cur * 2;
    if (next <= MAX && dist[next] > dist[cur]) {
      dist[next] = dist[cur];
      dq.push_front(next);
    }

    next = cur - 1;
    if (next >= 0 && dist[next] > dist[cur] + 1) {
      dist[next] = dist[cur] + 1;
      dq.push_back(next);
    }

    next = cur + 1;
    if (next <= MAX && dist[next] > dist[cur] + 1) {
      dist[next] = dist[cur] + 1;
      dq.push_back(next);
    }
  }

  cout << dist[k] << '\n';
  return 0;
}