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

문제 링크

13913번 - 숨바꼭질 4

설명

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

첫째 줄에 가장 빠른 시간을, 둘째 줄에 수빈이가 방문하는 위치를 순서대로 출력합니다.

접근법

각 이동이 1초씩 걸리므로 너비 우선 탐색(BFS)을 사용하여 가장 빠른 시간을 구합니다.

BFS는 시작점에서 가까운 위치부터 순서대로 탐색하므로, 목적지에 처음 도달했을 때가 바로 최단 시간입니다.

이동 경로를 기록하기 위해, 각 위치에 처음 도달했을 때 어디에서 왔는지를 저장해둡니다.

현재 위치에서 세 가지 선택(X-1, X+1, 2×X) 중 아직 방문하지 않은 위치로 이동할 때, 그 새로운 위치의 이전 위치를 현재 위치로 기록합니다.

목적지에 도달하면 탐색을 종료하고, 저장해둔 이전 위치 정보를 따라가며 시작점까지 역으로 추적합니다.

이렇게 얻은 경로는 거꾸로 되어 있으므로 뒤집으면 시작점부터 목적지까지의 올바른 순서가 됩니다.

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

• 5 → 10 (×2) → 9 (-1) → 18 (×2) → 17 (-1)로 4초에 도달
• 경로: 5, 10, 9, 18, 17

이때 각 위치의 이전 위치를 기록하면:

• 10의 이전: 5
• 9의 이전: 10
• 18의 이전: 9
• 17의 이전: 18

17에서 역추적하면 17 → 18 → 9 → 10 → 5가 되고, 이를 뒤집으면 원하는 경로를 얻습니다.

관련 문제: [백준 12851] 숨바꼭질 2 (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];
      var parent = new int[MAX + 1];
      Array.Fill(dist, -1);

      var q = new Queue<int>();
      dist[n] = 0;
      parent[n] = n;
      q.Enqueue(n);

      while (q.Count > 0) {
        var cur = q.Dequeue();
        if (cur == k) break;
        
        var nexts = new[] { cur - 1, cur + 1, cur * 2 };
        foreach (var next in nexts) {
          if (next < 0 || next > MAX) continue;
          if (dist[next] != -1) continue;
          
          dist[next] = dist[cur] + 1;
          parent[next] = cur;
          q.Enqueue(next);
        }
      }

      Console.WriteLine(dist[k]);

      var path = new List<int>();
      var pos = k;
      while (true) {
        path.Add(pos);
        if (pos == parent[pos]) break;
        pos = parent[pos];
      }
      
      path.Reverse();
      Console.WriteLine(string.Join(' ', path));
    }
  }
}

C++

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

typedef vector<int> vi;
typedef queue<int> qi;

const int MAX = 100000;

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

  int n, k; cin >> n >> k;
  vi dist(MAX + 1, -1);
  vi parent(MAX + 1, -1);

  qi q;
  dist[n] = 0;
  parent[n] = n;
  q.push(n);

  while (!q.empty()) {
    int cur = q.front();
    q.pop();
    if (cur == k) break;
    
    int nexts[3] = {cur - 1, cur + 1, cur * 2};
    for (int next : nexts) {
      if (next < 0 || next > MAX) continue;
      if (dist[next] != -1) continue;
      
      dist[next] = dist[cur] + 1;
      parent[next] = cur;
      q.push(next);
    }
  }

  cout << dist[k] << '\n';
  
  vi path;
  int pos = k;
  while (true) {
    path.push_back(pos);
    if (pos == parent[pos]) break;
    pos = parent[pos];
  }
  
  reverse(path.begin(), path.end());
  for (size_t i = 0; i < path.size(); i++) {
    cout << path[i] << (i + 1 == path.size() ? '\n' : ' ');
  }

  return 0;
}