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

문제 링크

12851번 - 숨바꼭질 2

설명

수직선 위에서 수빈이와 동생의 초기 위치가 주어지고, 수빈이는 1초에 한 칸 앞으로, 한 칸 뒤로, 또는 현재 위치의 두 배 위치로 이동할 수 있을 때, 동생을 찾는 가장 빠른 시간과 그 시간으로 도달하는 방법의 수를 구하는 문제입니다.

수빈이와 동생의 초기 위치가 주어지며, 두 위치 모두 0 이상 100,000 이하입니다.

가장 빠른 시간을 첫째 줄에, 그 시간으로 동생을 찾는 방법의 수를 둘째 줄에 출력합니다.

접근법

각 이동이 1초씩 걸리므로 BFS를 사용하여 동생을 찾는 최단 시간을 구합니다.

최단 시간에 도달하는 방법의 수를 세기 위해, 방문 처리를 큐에서 꺼낸 후로 지연시켜 같은 시간에 목적지에 여러 경로가 도달할 수 있도록 합니다.

목적지에 처음 도착하면 그 시간을 최단 시간으로 기록하고, 이후 동일한 시간에 도착할 때마다 방법의 수를 증가시킵니다.

BFS는 시간 순서대로 탐색하므로, 최단 시간 이후에는 더 이상 경로를 세지 않아도 됩니다.

예를 들어, 수빈이가 5에 있고 동생이 17에 있다면 5 → 10 → 9 → 18 → 17, 5 → 4 → 8 → 16 → 17 등 서로 다른 경로로 4초에 도달할 수 있으며, 이러한 모든 방법의 개수를 세어 출력합니다.

---

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  struct Info {
    public int pos, time;
  }

  class Program {
    const int MAX = 100001;

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

      var visited = new bool[MAX];
      var q = new Queue<Info>();
      q.Enqueue(new Info { pos = n, time = 0 });
      visited[n] = true;

      var minTime = 0;
      var ways = 0;

      while (q.Count > 0) {
        var cur = q.Dequeue();

        visited[cur.pos] = true;

        if (minTime != 0 && minTime == cur.time && cur.pos == k) ways++;

        if (minTime == 0 && cur.pos == k) {
          minTime = cur.time;
          ways++;
        }

        if (cur.pos + 1 < MAX && !visited[cur.pos + 1])
          q.Enqueue(new Info { pos = cur.pos + 1, time = cur.time + 1 });

        if (cur.pos - 1 >= 0 && !visited[cur.pos - 1])
          q.Enqueue(new Info { pos = cur.pos - 1, time = cur.time + 1 });

        if (2 * cur.pos < MAX && !visited[2 * cur.pos])
          q.Enqueue(new Info { pos = 2 * cur.pos, time = cur.time + 1 });
      }

      Console.WriteLine(minTime);
      Console.WriteLine(ways);
    }
  }
}

C++

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

#define MAX 100001

struct Info {
  int pos, time;
};

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

  int posSu, posSib; cin >> posSu >> posSib;

  bool visited[MAX] = {false};
  queue<Info> q;
  q.push({posSu, 0});
  visited[posSu] = true;

  int minTime = 0;
  int cntWay = 0;

  while (!q.empty()) {
    Info cur = q.front();
    q.pop();

    visited[cur.pos] = true;

    if (minTime != 0 && minTime == cur.time && cur.pos == posSib) cntWay++;

    if (minTime == 0 && cur.pos == posSib) {
      minTime = cur.time;
      cntWay++;
    }

    if (cur.pos + 1 < MAX && !visited[cur.pos + 1])
      q.push({cur.pos + 1, cur.time + 1});

    if (cur.pos - 1 >= 0 && !visited[cur.pos - 1])
      q.push({cur.pos - 1, cur.time + 1});

    if (2 * cur.pos < MAX && !visited[2 * cur.pos])
      q.push({2 * cur.pos, cur.time + 1});
  }

  cout << minTime << "\n" << cntWay << "\n";

  return 0;
}