재귀함수를 복습하면서 간단하지만 핵심개념이라 할 수 있는 하노이의 탑에 대해서 설명합니다.

---

하노이의 탑(Tower of Hanoi)은 퍼즐의 일종입니다.

세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고,

퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있을 때.

게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓습니다.

조건

• 세개의 기둥과 서로 다른 크기인 N개의 원반

• 원반들은 3개의 기둥 중 하나에 꽂혀있어야하고, 자신보다 작은 원반위에 꽂을 수 없음

알고리즘

기둥 1에서 N개의 원반을 기둥2를 이용해 기둥3으로 옮기는 알고리즘

• 기둥 1에서 n-1개의 원반을 기둥3을 이용하여 기둥 2로 옮긴다.

• 기둥 1에서 1개의 원반을 기둥3으로 옯긴다.

• 기둥 2에서 n-1개의 원반을 기둥 1을 이용하여 기둥 3으로 옮긴다.

C를 이용한 풀이

#include <stdio.h>

void move(int from, int to)
{
    printf("\nMove from %d to %d", from, to);
}

void hanoi(int n, int from, int by, int to)
{
    if (n == 1)
        move(from, to);
    else
    {
        hanoi(n - 1, from, to, by);
        move(from, to);
        hanoi(n - 1, by, from, to);
    }
}
int main()
{
    int N;
    scanf("%d", &N);
    hanoi(N, 1, 2, 3);
 
    return 0;
}

C++를 이용한 풀이

C랑 같다.

#include <stdio.h>

void hanoi(int n, int from, int tmp, int to) {
    if (n == 1)
        printf("\nMove from %d to %d", from, to);
    else
    { 
        hanoi(n - 1, from, to, tmp);
        printf("\nMove from %d to %d", from, to);
        hanoi(n - 1, tmp, from, to);
    }
}
int main()
{
    int N;
    scanf("%d", &N);
    hanoi(N, 1, 2, 3);
 
    return 0;
}

Java를 이용한 풀이

public class Hanoi {
    public static void main(String[] args) {
        hanoi2(5, 1, 2, 3);//그냥 N을 5로 설정함
    }
    static void hanoi2(int number, int from, int by, int to) {
        if (number == 1)
        {
            System.out.println("Move from "+from+ "to"+to);
            return;
        }
        hanoi2(number - 1, from, to, by);
        System.out.println("Move from "+from+ "to"+to);
        hanoi2(number - 1, by, from, to);
    }

}

---