[자료구조] 10 하노이타워

✔️ 하노이타워

하노이 타워

📌 조건

1. 한번에 하나의 원판만 옮길 수 있다

2. 큰 원판이 작은 원판 위에 올라 갈 순 없다

 

 

👉 알고리즘은 다음과 같다 

세개의 기둥 A,B,C 가 있고 기둥 A 에서 B로 n개의 원판을 옮긴다고 할 때

1. 기둥 A에서 n-1개개의 원판을 C로 먼저 옮긴다 

2. 기둥 A에 남은 1개 B로 옮긴다

3. 기둥 C에 있는 n-1개의 기둥을 재귀함수를 이용해 기둥 B로 옮긴다 (1-2번처럼)

❗️이 알고리즘은 원판의 수가 n개일 때 2^n -1 이동 횟수 필요 

 

 

원판의 수가 1개라면 기둥 a->b 로 이동시키고 종료

원판의 수가 2개 이상이라면 n-1개의 원판을 기둥 c->b로 이동시킴

c = 6-a-b (Ex. a=1,b=2 일때 c 는 6-1-2=3번기둥이다)

 

// #include <stdio.h>

int count = 0;
void htower(int n, int a, int b);

int main(){
    int n;
    count =0;
    printf("how many disk? :");
    scanf("%d", &n); //disk의 갯수 받기
    htower(n,1,2); //n개를 1번 기둥에서 2번 기둥으로 옮기기
    printf("#how many moves for %d disks? : %d", n, count);
}

void htower(int n, int a, int b){
    int c;
    count++; //움직이는 횟수 ++
    if(n==1){
        printf("Disk %d, moved from (%d) to (%d)\n", n, a, b);
    }
    else{
        c = 6-1-b; //첫번째로 비어있는 기둥
        htower(n-1, a, c);
        printf("Disk %d, moved from (%d) to (%d)\n", n, a, b);
        htower(n-1, c, b);
    }
}

👆 만약 3개의 원판일 경우,

위 코드대로 알고리즘이 실행된다면

htower(3,1,2) 

count =1 이 되고 c=3, htower(2,1,3) 실행 

count = 2 가 되고 c=2, htower(1,1,2) 실행

count =3 이 되고 print => Disk 1, moved from 1 to 2

재귀적으로 계속 진행..

 

//결과

Disk 1, moved from (1) to (2)

Disk 2, moved from (1) to (3)

Disk 1, moved from (2) to (3)

Disk 3, moved from (1) to (2)

Disk 1, moved from (3) to (3)

Disk 2, moved from (3) to (2)

Disk 1, moved from (3) to (2)

#how many moves for 3 disks? : 7