문제 출처

1. 문제설명

• 대표적인 재귀 문제 하노이의 탑
• 3개의 기둥과 N개의 원판이 주어질 때,
• 하노이의 탑 규칙을 적용한 경로를 구하는 문제
• 규칙
  • 한 번에 하나의 원판만 옮길 수 있다.
  • 큰 원판이 작은 원판 위에 올라가 있으면 안된다.
  • 즉, N이 3이면 가장 왼쪽 기둥에 위부터 1, 2, 3 크기의 원판이 있는 것
• 문제 분류
  • Implementation, Simulation

2. 알고리즘 설계

• N개의 원판을 옮기기
  • N-1개의 원판을 2번째 기둥으로 옮기고,
    • hanoi(n-1, from, by, to)
  • 1번 기둥에서 3번 기둥으로 N번째 원판을 옮긴다.
    • answer.push_back({from, to}) // 기록
  • 2번째 기둥에 위치한 N-1개의 원판을 3번 기둥으로 옮긴다.
    • hanoi(n-1, by, to, from)

3. 전체 코드

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

vector<vector<int>> answer;

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

vector<vector<int>> solution(int n) {
    hanoi(n, 1, 3, 2);
    return answer;
}

4. 소감

• 학부 시절, 알고리즘 수업 때 거의 맨 앞에 나오는 알고리즘이다.
• 그 당시 반복 형태의 코드는 생각보다 엄청 복잡했었고,
• 복잡한 로직을 재귀로 간단히 풀이했던 것이 기억났다.
• ‘모든 반복의 형태는 재귀로 변환 가능하고, 그 역도 가능하다.’