[백준] 11729 하노이 탑 이동 순서 - C

 

https://www.acmicpc.net/problem/11729

---

 

n개의 원반을 다른 기둥에 옮기는것이 목표인 전형적인 하노이 탑 문제이다.

이동 순서또한 출력해야 하기 때문에 단순히 수식만 써서는 풀기 어렵다.

 

n개의 원반을 다른 기둥으로 옮기는 과정은 크게 3개로 나눌 수 있다. (1번째 기둥에서 3번째 기둥으로 옮기려 할 때)

 

1. 1번째 기둥에서 n-1개의 원반을 2번째 기둥으로 옮긴다.

2. 1번째 기둥의 가장 큰 원반을 3번째 기둥으로 옮긴다.

3. 2번째 기둥에 있는 n-1개의 원반을 3번째 기둥으로 옮긴다.

 

이걸 코드로 작성하면

#include <stdio.h>

void hanoi(int n, int start, int end, int mid);

int main() {

    int n;
    scanf("%d", &n);
    printf("%d\n", (1 << n) - 1);
    hanoi(n, 1, 3, 2);
    
    return 0;
}


void hanoi(int n, int start, int end, int mid) {

    if (n == 0) {
        return;
    }
    else {
        hanoi(n - 1, start, mid, end);//1번째 과정
        printf("%d %d\n", start, end);//2번째 과정
        hanoi(n - 1, mid, end, start);//3번째 과정
    }
}

 

이런식으로 작성할 수 있다.

참고로 이동 횟수는 2^n-1이기 때문에 시프트 연산을 사용하여 간단히 구하였다.

---