[C, Java, Python] 하노이의 탑(Tower of Hanoi) 코드 시리즈

 

 

 

 

 

 

하노이의 탑 문제는 다음과 같은 규칙을 가진 퍼즐입니다:

1. 세 개의 기둥(A, B, C)과 여러 개의 원판이 있습니다.
2. 원판은 크기가 다르며, 작은 원판이 큰 원판 위에 놓일 수는 없습니다.
3. 처음에는 모든 원판이 기둥 A에 쌓여 있습니다.
4. 목표는 모든 원판을 기둥 C로 옮기는 것입니다, 단, 한 번에 하나의 원판만 옮길 수 있으며, 각 원판은 항상 위쪽에 있는 원판보다 작은 원판 위에만 놓일 수 있습니다.

하노이의 탑 문제를 해결하기 위한 C 코드를 작성하고 설명하겠습니다.

 

■ 하노이의 탑 문제를 해결하는 C 코드

#include <stdio.h>

// 하노이의 탑을 해결하는 재귀 함수
void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        // 원판이 하나만 남았을 때, 직접적으로 목표 기둥으로 이동
        printf("Move disk 1 from %c to %c\n", from, to);
        return;
    }
    // n-1개의 원판을 보조 기둥으로 이동
    hanoi(n - 1, from, aux, to);
    // 남은 원판을 목표 기둥으로 이동
    printf("Move disk %d from %c to %c\n", n, from, to);
    // 보조 기둥에 있는 원판을 목표 기둥으로 이동
    hanoi(n - 1, aux, to, from);
}

int main() {
    int n; // 원판의 개수
    printf("Enter the number of disks: ");
    scanf("%d", &n); // 사용자로부터 원판의 개수 입력 받기
    // 하노이 함수 호출
    hanoi(n, 'A', 'C', 'B');
    return 0;
}

 

코드 설명

1. 함수 hanoi:
   • 이 함수는 하노이의 탑 문제를 해결하는 재귀 함수입니다.
   • 매개변수는 n (현재 처리할 원판의 개수), from (원판을 이동할 시작 기둥), to (원판을 이동할 목표 기둥), aux (보조 기둥)입니다.
   • 기저 조건: 원판이 하나일 경우 직접적으로 이동합니다 (n == 1).
   • 재귀 호출:
     • 첫 번째 호출: n-1개의 원판을 보조 기둥으로 이동 (hanoi(n - 1, from, aux, to)).
     • 현재 원판을 목표 기둥으로 이동합니다.
     • 두 번째 호출: 보조 기둥에 있는 n-1개의 원판을 목표 기둥으로 이동 (hanoi(n - 1, aux, to, from)).
2. main 함수:
   • 사용자로부터 원판의 개수를 입력받습니다.
   • 입력받은 원판의 개수와 함께 하노이의 탑 문제를 해결하기 위해 hanoi 함수를 호출합니다.
   • 기둥은 각각 'A', 'B', 'C'로 명명되며, 처음에는 모든 원판이 기둥 A에 있으며, 목표는 기둥 C로 이동하는 것입니다.

이 코드는 입력된 원판의 개수에 따라 하노이의 탑 문제를 해결하는 방법을 출력합니다. 원판을 이동시키는 과정을 단계별로 출력하여 해결 과정을 쉽게 따라갈 수 있도록 합니다.

 

■ 하노이의 탑 문제를 해결하는 자바 코드

import java.util.Scanner;

public class TowerOfHanoi {

    // 하노이의 탑을 해결하는 재귀 함수
    public static void hanoi(int n, char fromPole, char toPole, char auxPole) {
        if (n == 1) {
            // 원판이 하나만 남았을 때, 직접적으로 목표 기둥으로 이동
            System.out.println("Move disk 1 from " + fromPole + " to " + toPole);
            return;
        }
        // n-1개의 원판을 보조 기둥으로 이동
        hanoi(n - 1, fromPole, auxPole, toPole);
        // 남은 원판을 목표 기둥으로 이동
        System.out.println("Move disk " + n + " from " + fromPole + " to " + toPole);
        // 보조 기둥에 있는 원판을 목표 기둥으로 이동
        hanoi(n - 1, auxPole, toPole, fromPole);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the number of disks: ");
        int n = scanner.nextInt(); // 사용자로부터 원판의 개수 입력 받기
        scanner.close(); // Scanner 객체 닫기

        // 하노이 함수 호출
        hanoi(n, 'A', 'C', 'B');
    }
}

 

코드 설명

1. 함수 hanoi:
   • 이 함수는 하노이의 탑 문제를 해결하는 재귀 함수입니다.
   • 매개변수는 n (현재 처리할 원판의 개수), fromPole (원판을 이동할 시작 기둥), toPole (원판을 이동할 목표 기둥), auxPole (보조 기둥)입니다.
   • 기저 조건: 원판이 하나일 경우 직접적으로 이동합니다 (n == 1).
   • 재귀 호출:
     • 첫 번째 호출: n-1개의 원판을 보조 기둥으로 이동 (hanoi(n - 1, fromPole, auxPole, toPole)).
     • 현재 원판을 목표 기둥으로 이동합니다 (System.out.println("Move disk " + n + " from " + fromPole + " to " + toPole)).
     • 두 번째 호출: 보조 기둥에 있는 n-1개의 원판을 목표 기둥으로 이동 (hanoi(n - 1, auxPole, toPole, fromPole)).
2. main 함수:
   • 사용자로부터 원판의 개수를 입력받습니다.
   • 입력받은 원판의 개수와 함께 하노이의 탑 문제를 해결하기 위해 hanoi 함수를 호출합니다.
   • 기둥은 각각 'A', 'B', 'C'로 명명되며, 처음에는 모든 원판이 기둥 A에 있으며, 목표는 기둥 C로 이동하는 것입니다.

 

■ 하노이의 탑 문제를 해결하는 파이썬 코드

def hanoi(n, from_pole, to_pole, aux_pole):
    if n == 1:
        # 원판이 하나만 남았을 때, 직접적으로 목표 기둥으로 이동
        print(f"Move disk 1 from {from_pole} to {to_pole}")
        return
    # n-1개의 원판을 보조 기둥으로 이동
    hanoi(n - 1, from_pole, aux_pole, to_pole)
    # 남은 원판을 목표 기둥으로 이동
    print(f"Move disk {n} from {from_pole} to {to_pole}")
    # 보조 기둥에 있는 원판을 목표 기둥으로 이동
    hanoi(n - 1, aux_pole, to_pole, from_pole)

def main():
    n = int(input("Enter the number of disks: "))  # 사용자로부터 원판의 개수 입력 받기
    hanoi(n, 'A', 'C', 'B')

if __name__ == "__main__":
    main()

코드 설명

1. 함수 hanoi:
   • 이 함수는 하노이의 탑 문제를 해결하는 재귀 함수입니다.
   • 매개변수는 n (현재 처리할 원판의 개수), from_pole (원판을 이동할 시작 기둥), to_pole (원판을 이동할 목표 기둥), aux_pole (보조 기둥)입니다.
   • 기저 조건: 원판이 하나일 경우 직접적으로 이동합니다 (n == 1).
   • 재귀 호출:
     • 첫 번째 호출: n-1개의 원판을 보조 기둥으로 이동 (hanoi(n - 1, from_pole, aux_pole, to_pole)).
     • 현재 원판을 목표 기둥으로 이동합니다 (print(f"Move disk {n} from {from_pole} to {to_pole}")).
     • 두 번째 호출: 보조 기둥에 있는 n-1개의 원판을 목표 기둥으로 이동 (hanoi(n - 1, aux_pole, to_pole, from_pole)).
2. main 함수:
   • 사용자로부터 원판의 개수를 입력받습니다.
   • 입력받은 원판의 개수와 함께 하노이의 탑 문제를 해결하기 위해 hanoi 함수를 호출합니다.
   • 기둥은 각각 'A', 'B', 'C'로 명명되며, 처음에는 모든 원판이 기둥 A에 있으며, 목표는 기둥 C로 이동하는 것입니다.