하노이탑
IT위키
시간복잡도 : O(2^n)
출처 : [1]
// PSEUDO CODE FROM A TO B
void Hanoi(int N, int A, int TO, int B) {
if (N == 1) {
print(A->B);
return;
}
Hanoi(N - 1, A, B, TO);
print(A -> B);
Hanoi(N - 1, TO, A, B);
/*
모르면 외우자...
N : 원판의 개수
A : 출발지
B : 옮기기 위해 이동해야 장소
C : 목적지
*/
void Hanoi(int N, int A, int B, int C) {
// 이동할 원반의 수가 1개
if (N == 1) {
print(A + " " + C + "\n");
return;
}
// A -> B(N-1개)
Hanoi(N - 1, A, C, B);
// A->C(1개)
print(A + " " + C + "\n");
// B->C(N-1개)
Hanoi(N - 1, B, A, C);
}
출처 : [2]
