[자료구조] ep2+) 하노이 탑 구현

하노이 탑이란?

A, B, C는 각각 세 개의 기둥을 나타낸다

 

B 기둥을 이용해서 A 기둥에 놓인 크기가 다른 원판을 C 기둥으로 옮기는 문제이다. 이때 원판은 한 번에 한 개씩만 옮길 수 있으며, 작은 원판 위에 큰 원판이 놓일 수 없다.

+ 이동횟수 공식은 (2^n - 1) 회이다 e.g. n = 1인 경우 1회의 이동, n = 2인 경우 3회의 이동, n = 3인 경우, 7회의 이동 

 

 

 

 

 

 

문제)

원반의 개수 N을 입력받아, 하노이 탑 문제의 수행과정을 출력하는 프로그램을 작성해라

 

 

test case

 

 

 

의사코드)

"이중재귀"로 구현된다

n: 이동해야 할 원반 수

from: 출발 기둥

aux: 보조 기둥

to: 목표 기둥

 

 

모식도)

 

 

//A에 1~N 쌓여있음
A     B     C
1
2
.
.
N

//N-1개를 A에서 C를 거쳐 B로 이동
A     B     C
N     1
        2
        .
        .
      N-1

//A에서 C로 원반N 이동
A     B     C
       1      N
       2
       .
       .
     N-1

//B에서 A를 거쳐 나머지 N-1개 C로이동
A     B     C
               1
               2
               .
               .
               N

 

 

 

 

 

의사코드와 모식도를 보고 코드를 작성하면 원반이 쌓이는 메카니즘을 이해할 수 있을 것이다

하지만 재귀함수가 호출스택에 쌓이는 원리는 이해하기 어려울 것이다

rHanoi(N - 1, A, C, B);
printf("%c %c\n", A, C);
rHanoi(N - 1, B, A, C); 

이 부분이 호출스택에 어떻게 계속해서 쌓이는지 직접 종이에 한번 다 일일이 써보기를 추천한다 (한 30분은 걸린다는 마음가짐으로)

그렇게 삽질을 하고 나면 분명 보이는 시야가 달라질 것이다 그런 후에 이 영상의 3분 35초 이후부터 보는 걸 추천한다 (처음부터 다 보면 베스트)

https://www.youtube.com/watch?v=aPYE0anPZqI

하노이탑 관련 영상을 다 찾아봤는데 이만한 영상이 없다

 

 

 

 

 

 

 

(전체코드)

#include <stdio.h>
#pragma warning (disable:4996)

// A, B, C는 각각 세 개의 기둥을 나타낸다
// rHanoi 함수의 목적: A기둥의 모든 디스크를 C기둥으로 이동시킨다
void rHanoi(int N, char A, char B, char C) { 
    // N이 1이라면, 그냥 A 기둥에서 C 기둥으로 옮기면 된다
    if (N == 1) {
        printf("%c %c\n", A, C); 
        return;
    }
    // N이 1보다 크다면, N-1개의 원반을 기둥 A에서 B로 옮기고
    // 나머지 하나(가장 큰 디스크)를 기둥 A에서 C로 옮긴 후
    // 다시 N-1개를 기둥 B에서 C로 옮기는 재귀적인 과정을 수행
    rHanoi(N - 1, A, C, B); // N-1개의 디스크를 A기둥 -> B기둥 이동 반복 (C기둥이 보조역할)
    printf("%c %c\n", A, C); // A기둥의 나머지 하나(가장 큰 디스크)를 C기둥으로 이동
    rHanoi(N - 1, B, A, C); // N-1개의 디스크를 B기둥 -> C기둥 이동 반복 (A기둥이 보조역할)
    return;
}

void hanoi(int N) {
    rHanoi(N, 'A', 'B', 'C');
    return;
}

int main(void) {
    int N;

    scanf("%d", &N);

    hanoi(N);

    return 0;
}

 

 

 

 

 

 

 

 

 

 

 

참고 및 출처: 데이터 구조 원리와 응용(국형준교수님)