[백준 11729] 하노이 탑 이동 순서 (C#, C++) - soo:bak

문제 링크

11729번 - 하노이 탑 이동 순서

설명

하노이 탑의 규칙을 따라 원판을 옮기는 최소 횟수와 그 과정을 출력하는 문제입니다.

• 세 개의 장대와 크기가 다른 N개의 원판이 있습니다.
• 한 번에 한 개의 원판만 옮길 수 있으며, 큰 원판 위에 작은 원판을 놓을 수 없습니다.
• 첫 번째 장대에 쌓인 모든 원판을 세 번째 장대로 옮겨야 하며, 이동 횟수는 최소가 되어야 합니다.

접근법

하노이 탑의 핵심은 다음과 같은 재귀 구조에 있습니다:

• N개의 원판을 옮기기 위해서는
  • 위의 N - 1개의 원판을 보조 기둥으로 옮기고,
  • 가장 큰 원판을 목표 기둥으로 이동한 다음,
  • 다시 N - 1개의 원판을 그 위에 옮깁니다.

이 과정을 재귀적으로 반복하면 총 이동 횟수는 \(2^N - 1\)이 됩니다.

모든 이동은 (출발 기둥 → 도착 기둥)의 형태로 출력합니다.

참고 : 하노이의 탑 이동 문제 - soo:bak

---

Code

C#

using System;
using System.Collections.Generic;
using System.Text;

class Program {
  static int count = 0;
  static List<(int from, int to)> moves = new();

  static void Hanoi(int n, int from, int via, int to) {
    if (n == 0) return;
    Hanoi(n - 1, from, to, via);
    moves.Add((from, to));
    count++;
    Hanoi(n - 1, via, from, to);
  }

  static void Main() {
    int n = int.Parse(Console.ReadLine());
    Hanoi(n, 1, 2, 3);

    var sb = new StringBuilder();
    sb.AppendLine(count.ToString());
    foreach (var (from, to) in moves)
      sb.AppendLine($"{from} {to}");

    Console.Write(sb.ToString());
  }
}

C++

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef vector<pi> vpi;

int cnt = 0;
vpi moves;

void hanoi(int n, int from, int by, int to) {
  if (n == 0) return;
  hanoi(n - 1, from, to, by);
  cnt++;
  moves.push_back({from, to});
  hanoi(n - 1, by, from, to);
}

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

  int n; cin >> n;
  hanoi(n, 1, 2, 3);

  cout << cnt << "\n";
  for (const auto& [from, to] : moves)
    cout << from << " " << to << "\n";

  return 0;
}