백준 11729 하노이 탑 이동 순서 [C++]

작성일 | In |

Problem : 하노이 탑 이동 순서

유형 : 재귀

문제 해석

  • 하노이탑에서 판의 이동 횟수와 이동 순서를 구하라.

해결 전략

  • 재귀적으로 분할해서 해결한다.
  • 하노이탑을 옮기는 최적의 방법이 존재한다.
      1. 맨 아래판을 제외한 나머지판을 빈공간에 옮긴다.
      1. 맨 아래판을 목적지 공간으로 옮긴다.
      1. 1에서 옮긴 빈공간으로 옮긴 나머지판을 목적지 공간으로 옮긴다.

설계, 구현

  • 판의 총 이동 횟수는 정해져있다.
    • 판이 N개라면 2^N-1번을 움직여야 한다.
  • 현재 옮겨야할 판의 개수, 시작지점, 빈 공간, 목적지 공간을 본다.
    • 옮겨야할 판의 개수를 본다.
      • 1개 라면 그냥 목적지로 바로 옮긴다.
      • 2개 이상이라면 n-1 개를 빈 공간 으로 옮긴다.
        • 이때 빈 공간이 목적지 가 되므로, 이 단계에서의 빈공간은 목적지 공간 이 된다.

주의할 점

  • 없음

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

void hanoiMove(int plateNum, int start, int mid, int end) {
    if (plateNum == 1) {
        cout << start << " " << end << "\n";
        return; 
    }
    hanoiMove(plateNum - 1, start, end, mid);
    hanoiMove(1, start, mid, end);
    hanoiMove(plateNum - 1, mid, start, end);
}

void solve() {
    int plateNum;
    cin >> plateNum;

    cout << (1 << plateNum) - 1 << "\n";
    hanoiMove(plateNum, 1, 2, 3);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    solve();

    return 0;
}

피드백

  • 없음