하노이의 탑

문제 이해

하노이의 탑은 한 기둥에 쌓인 원판을 다른 기둥으로 모두 옮기는 퍼즐이다.
원판은 한 번에 하나만 옮길 수 있다.
각 기둥에서는 가장 위에 있는 원판만 꺼낼 수 있다.
큰 원판은 작은 원판 위에 올릴 수 없다.

하노이의 탑 플레이하기

원판 개수별 이동 과정

원판이 n개일 때 최소 이동 횟수는 2^n - 1이다.

A: 시작 기둥
B: 보조 기둥
C: 목표 기둥

원판 크기:

• 소 → 가장 작은 원판
• 중 → 작은 다음 크기
• 대 → 큰 원판
• 특 → 가장 큰 원판

원판 1개

1. A -> C 소
   • A: [ ] B: [ ] C: [소]

원판 2개

1. A -> B 소
   • A: [중] B: [소] C: [ ]
2. A -> C 중
   • A: [ ] B: [소] C: [중]
3. B -> C 소
   • A: [ ] B: [ ] C: [중,소]

원판 3개

1. A -> C 소
   • A: [대,중] B: [ ] C: [소]
2. A -> B 중
   • A: [대] B: [중] C: [소]
3. C -> B 소
   • A: [대] B: [중,소] C: [ ]
4. A -> C 대
   • A: [ ] B: [중,소] C: [대]
5. B -> A 소
   • A: [소] B: [중] C: [대]
6. B -> C 중
   • A: [소] B: [ ] C: [대,중]
7. A -> C 소
   • A: [ ] B: [ ] C: [대,중,소]

원판 4개

1. A -> B 소
   • A: [특,대,중] B: [소] C: [ ]
2. A -> C 중
   • A: [특,대] B: [소] C: [중]
3. B -> C 소
   • A: [특,대] B: [ ] C: [중,소]
4. A -> B 대
   • A: [특] B: [대] C: [중,소]
5. C -> A 소
   • A: [특,소] B: [대] C: [중]
6. C -> B 중
   • A: [특,소] B: [대,중] C: [ ]
7. A -> B 소
   • A: [특] B: [대,중,소] C: [ ]
8. A -> C 특
   • A: [ ] B: [대,중,소] C: [특]
9. B -> C 소
   • A: [소] B: [대,중] C: [특]
10. B -> A 중
    • A: [중] B: [대] C: [특,소]
11. C -> A 소
    • A: [중,소] B: [대] C: [특]
12. B -> C 대
    • A: [중,소] B: [ ] C: [특,대]
13. A -> B 소
    • A: [중] B: [소] C: [특,대]
14. A -> C 중
    • A: [ ] B: [소] C: [특,대,중]
15. B -> C 소
    • A: [ ] B: [ ] C: [특,대,중,소]

풀이

풀이 코드에서도 A는 시작 기둥, B는 보조 기둥, C는 목표 기둥으로 사용한다.
출력의 disk 1은 가장 작은 원판을 뜻한다.
숫자가 커질수록 더 큰 원판을 뜻하므로 원판이 3개라면 disk 3이 가장 큰 원판이다.

이동 과정 출력하기

#include <stdio.h>

void hanoi(int n, char from, char via, char to)
{
    if (n == 0)
        return;

    hanoi(n - 1, from, to, via);
    printf("disk %d: %c -> %c\n", n, from, to);
    hanoi(n - 1, via, from, to);
}

int main(void)
{
    int n = 3;

    hanoi(n, 'A', 'B', 'C');

    return 0;
}

이동 과정 저장하기

#include <stdio.h>
#include <stdlib.h>

typedef struct s_step
{
    int  disk;
    char from;
    char to;
} t_step;

void hanoi(int disk_count, char from, char via, char to, t_step steps[], int* step_index)
{
    if (disk_count == 0)
        return;

    hanoi(disk_count - 1, from, to, via, steps, step_index);

    steps[*step_index].disk = disk_count;
    steps[*step_index].from = from;
    steps[*step_index].to = to;
    (*step_index)++;

    hanoi(disk_count - 1, via, from, to, steps, step_index);
}

int main(void)
{
    int disk_count = 3;
    int step_count = (1 << disk_count) - 1;
    int step_index = 0;
    t_step* steps = malloc(sizeof(t_step) * step_count);

    hanoi(disk_count, 'A', 'B', 'C', steps, &step_index);

    for (int i = 0; i < step_count; i++)
        printf("disk %d: %c -> %c\n", steps[i].disk, steps[i].from, steps[i].to);

    free(steps);

    return 0;
}