하노이탑 문제

---

1. C언어 코드

#include <stdio.h>

// 하노이탑 함수
void hanoi(int n, char from, char to, char via) {
    if (n == 1) {
        printf("원판 1을 %c에서 %c로 이동\n", from, to);
        return;
    }

    // 1단계: n-1개를 보조 기둥(via)로 이동 (to는 목표지만 잠깐 보조 역할)
    hanoi(n - 1, from, via, to);

    // 2단계: 가장 큰 원판 1개를 목적지(to)로 이동
    printf("원판 %d을 %c에서 %c로 이동\n", n, from, to);

    // 3단계: n-1개를 보조 기둥에서 목적지로 이동 (from은 이제 보조 역할)
    hanoi(n - 1, via, to, from);
}

int main() {
    int n;
    printf("원판의 개수 입력: ");
    scanf("%d", &n);

    printf("\n하노이탑 이동 순서:\n");
    hanoi(n, 'A', 'C', 'B');
    return 0;
}

 

---

2. 동작 원리

2.1 하노이탑 문제란?

 

• 세 개의 기둥(A, B, C)과 크기가 다른 원판 n개가 있다.
• 처음에는 모든 원판이 A 기둥에 큰 것부터 작은 순서로 쌓여 있음.
• 모든 원판을 C 기둥으로 옮겨야 함.
• 조건:
  1. 한 번에 한 개의 원판만 옮길 수 있다.
  2. 큰 원판이 작은 원판 위에 놓일 수 없다.
  3. 항상 위에 있는 원판만 옮길 수 있다.

 

 

2.2 함수 매개변수 의미 

void hanoi(int n, char from, char to, char via)

• n: 옮겨야 할 원판 개수
• from: 현재 원판이 쌓여 있는 출발 기둥
• to: 원판을 옮길 목적지 기둥
• via: 보조 기둥 (임시로 사용)

 

 

2.3 재귀 동작

기본 아이디어:

• n개의 원판을 옮기는 문제를, 작은 문제로 나누어 n-1개의 원판을 먼저 옮기고, 마지막으로 큰 원판 하나를 옮긴다.

순서:

1. n-1개를 보조 기둥으로 옮김
   • 이 때 to는 잠깐 보조 역할을 한다.

hanoi(n - 1, from, via, to);

 

 

2. 가장 큰 원판을 목적지로 옮기기

printf("원판 %d을 %c에서 %c로 이동\n", n, from, to);

 

3. n-1개를 보조 기둥에서 목적지 기둥으로 옮기기

• 이 때 from 은 보조 기둥 역할을 한다.

hanoi(n - 1, via, to, from);

 

즉, 3개로 기둥을 가정하고 해결하려면 A, B, C 기둥이 있을 때 

모든 원판을 제일 큰 원판 뻬고 n-1개를 B로 옮기고 다시 B 에서 C로 옮기면 된다. 

그 옮기는 중간에서 출발지, 목적지를 제외한 기둥은 보조 기둥이 되는 것이다. 

 

처음에는 이해하기 매우 어려우므로 중단점 걸어놓고 차근차근 코드의 흐름을 분석하면 됨