[Programmers] 하노이의 탑

하노이의 탑

1. 한 번에 하나의 원판만 옮길 수 있습니다.
2. 큰 원판이 작은 원판 위에 있어서는 안됩니다.
   하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.
   1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.

풀이

전형적인 재귀 문제이다.
예를 들어, 3개의 원판을 전부 1 -> 3번 기둥으로 이동해야 한다.

1. 2개의 원판을 1 -> 2로 이동이 목표
   a. 1개의 원판을 1 -> 3로 이동
   b. 2번 원판을 1 -> 2로 이동
   c. 1개의 원판을 3 -> 2로 이동
2. 3번 원판을 1 -> 3로 이동
3. 2개의 원판을 2 -> 3로 이동이 목표
   a. 1개의 원판을 2 -> 1로 이동
   b. 2번 원판을 2 -> 3로 이동
   c. 1개의 원판을 1 -> 3로 이동

일반화하면, 아래와 같다.

1. n-1개의 원판을 i -> 6-i-j로 이동이 목표
   ...
2. n번 원판을 i -> j로 이동
3. n-1개의 원판을 6-i-j -> j로 이동이 목표
   ...

코드

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

vector<vector<int>> answer;

void hanoi(int i, int j, int n){
    if(n==0) return;
    hanoi(i, 6-i-j, n-1);
    answer.push_back({i,j});
    hanoi(6-i-j, j, n-1);
}

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

정리

참고 영상