[Algorithm] C - 하노이의 탑(Towers Of Hanoi)

하노이의 탑(Towers Of Hanoi)

요약

• 큰 원반이 아래에서 차례로 위치할 수 있고, 최소한의 횟수로 마지막 기둥으로 원반을 옮기는 문제
• 가장 큰 원반을 제외하고 나머지 원반을 그룹으로 묶어 문제 해결에 접근
• 그룹은 원반 개수의 N - 1

하노이의 탑(Towers Of Hanoi)이란

하뇌의 탑은 작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에서 옮기는 문제이다.
모든 원반는 크기가 다르고 처음에는 모든 원반이 이 규칙에 맞게 첫 번째 기둥에 쌓여 있다.
이 상태에서 모든 원반을 세 번째 기둥으로 최소한의 횟수로 옮기는 문제이며, 원반은 1개씩만, 큰 원반을 작은 원반위에 쌓을 수 없다.

문제를 해결하기 위해 가장 큰 원반을 제외하고, 나머지 원반을 그룹으로 묶어 접근해야 한다.
그리고 총 3단계로 접근하여 문제를 해결한다.

1. 그룹을 시작 기둥에서 중간 기둥으로
2. 원반 3을 시작 기둥에서 목표 기둥으로
3. 그룹을 중간 기둥에서 목표 기둥으로

이 경우로 접근하면 원반 N개일 때도 동일하게 적용할 수 있다. 원반이 N개일 때 가장 큰 원반을 제외, N - 1개를 그룹으로 묶는다.

문제 풀이

1. 바닥 원반을 제외한 그룹(원반[1] ~ 원반[no - 1])을 시작 기둥에서 중간 기둥으로 옮김
2. 바닥 원반 no를 시작 기둥에서 목표 기둥으로 옮김
3. 바닥 원반을 제외한 그룹(원반[1] ~ 원반[no - 1])을 중간 기둥에서 목표 기둥으로 옮김

 

#include <stdio.h>

void move(int no, int x, int y);

int main()
{
    int n; // 원반 개수
    
    printf("원반 개수 : ");
    scanf("%d", &n);
    
    move(n, 1, 3);
    
    return 0;
}

// no : 원반 개수, x : 시작 기둥 번호, y : 목표 기둥 번호
void move(int no, int x, int y)
{
    // 그룹을 시작 기둥에서 중간 기둥으로
    if(no > 1) {
        move(no - 1, x, 6 - x - y);
    }
    
    printf("원반[%d]을 %d 기둥에서 %d 기둥으로 옮김\n", no, x, y);
    
    // 그룹을 중간 기둥에서 목표 기둥으로
    if(no > 1) {
        move(no - 1, 6 - x - y, y);
    }
    
}

 

실행 결과

원반 개수 : 3
원반[1]을 1 기둥에서 3 기둥으로 옮김
원반[2]을 1 기둥에서 2 기둥으로 옮김
원반[1]을 3 기둥에서 2 기둥으로 옮김
원반[3]을 1 기둥에서 3 기둥으로 옮김
원반[1]을 2 기둥에서 1 기둥으로 옮김
원반[2]을 2 기둥에서 3 기둥으로 옮김
원반[1]을 1 기둥에서 3 기둥으로 옮김


원반 개수 : 4
원반[1]을 1 기둥에서 2 기둥으로 옮김
원반[2]을 1 기둥에서 3 기둥으로 옮김
원반[1]을 2 기둥에서 3 기둥으로 옮김
원반[3]을 1 기둥에서 2 기둥으로 옮김
원반[1]을 3 기둥에서 1 기둥으로 옮김
원반[2]을 3 기둥에서 2 기둥으로 옮김
원반[1]을 1 기둥에서 2 기둥으로 옮김
원반[4]을 1 기둥에서 3 기둥으로 옮김
원반[1]을 2 기둥에서 3 기둥으로 옮김
원반[2]을 2 기둥에서 1 기둥으로 옮김
원반[1]을 3 기둥에서 1 기둥으로 옮김
원반[3]을 2 기둥에서 3 기둥으로 옮김
원반[1]을 1 기둥에서 2 기둥으로 옮김
원반[2]을 1 기둥에서 3 기둥으로 옮김
원반[1]을 2 기둥에서 3 기둥으로 옮김

https://github.com/JeHeeYu/Algorithm/tree/main/Recursion/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98%20%ED%83%91

GitHub - JeHeeYu/Algorithm: 알고리즘 문제 풀이

 

 

출처 : Do it! 자료구조와 함께 배우는 알고리즘 입문: C 언어 편