하노이탑

시간복잡도 : 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]