C - [백준 11729] 하노이 탑 이동 순서 (feat. 재귀적 사고)

[BOJ 4179]  하노이 탑 이동 순서

백준 문제 11729번 - 하노이 탑 이동 순서는 재귀 알고리즘을 사용하는 전형적인 문제입니다. 하노이의 탑은 퍼즐 게임으로, 크기가 서로 다른 원판을 특정 규칙에 따라 다른 기둥으로 옮기는 문제입니다.

---

문제 설명

하노이 탑 문제는 재귀 알고리즘의 대표적인 예제입니다. 이 문제에서는 n개의 원반을 1번 기둥에서 3번 기둥으로 옮기는 과정을 출력해야 합니다. 다음 규칙을 따라야 합니다:

1. 한 번에 하나의 원반만 옮길 수 있습니다.
2. 큰 원반은 작은 원반 위에 놓을 수 없습니다.
3. 2번 기둥을 보조 기둥으로 사용할 수 있습니다.

---

입력 및 출력 형식

• 입력:
  • 정수 n이 주어집니다. (1≤n≤20)
• 출력:
  1. 첫 번째 줄에 이동 횟수 n^2 - 1을 출력합니다.
  2. 이후 각 이동을 두 정수 a, b의 형식으로 출력합니다.
     (이는 원반을 a번 기둥에서 b번 기둥으로 옮긴다는 뜻입니다.)

 

예제 입력 1 

3

예제 출력 1 

7
1 3
1 2
3 2
1 3
2 1
2 3
1 3

---

Checkpoint

 

현재 저의 컴퓨팅적 사고에 "재귀적 사고"의 부재를 일깨워준 문제입니다. 절체적 코딩으로 해당 문제에 접근했으나 알고리즘 설계에 어려움을 겪어 허니C코드 님의 영상으로 하노이 탑에 관해 학습을 진행했으며 재귀적 사고의 확장에 대해 알게되었습니다. 하단의 링크는 해당 학습 자료입니다.

 

https://youtu.be/vq7dpFWpwAE?si=bNJeieid_xftz7-A

 

결국 재귀적 사고의 핵심은 문제의 규칙을 명확하게 정의해아한다는 것입니다. 규칙을 정확하게 진단하고 정의를 했으면 재귀의 기재조건(종료 조건)을 정의하면 됩니다.

재귀에 대한 포스트는 따로 상세하게 업로드 했습니다.

https://rnasterofmysea.tistory.com/61

[알고리즘] 단순 반복을 넘어서: 절차적 사고에 재귀를 더하다

 

하노이 탑의 규칙 찾기

하노이 탑은 원반의 개수 n에 따라 재귀적으로 문제를 해결합니다. 핵심 아이디어는 다음과 같습니다:

1. 상위 n−1n-1개의 원반을 보조 기둥으로 옮긴다.
2. 가장 큰 원반(n)을 목표 기둥으로 옮긴다.
3. 보조 기둥에 있는 n−1개의 원반을 목표 기둥으로 옮긴다.

이동 과정을 단계별로 분리

1. Step 1: n-1개의 원반을 출발 기둥 → 보조 기둥으로 이동.
2. Step 2: 가장 큰 원반(n)을 출발 기둥 → 목표 기둥으로 이동.
3. Step 3: n-1개의 원반을 보조 기둥 → 목표 기둥으로 이동.

---

코드 구현

#include <stdio.h>
#include <math.h>

/*
BOJ 11729 하노이 탑 이동 순서
https://www.acmicpc.net/problem/11729
*/

void hanoi(int n, int from, int to, int temp) {
    if (n == 1) {
        printf("%d %d\n", from, to); // 원판 1개를 옮기는 경우
        return;
    }
    // n-1개를 from에서 temp로 옮김
    hanoi(n - 1, from, temp, to);
    // 가장 큰 원판을 from에서 to로 옮김
    printf("%d %d\n", from, to);
    // n-1개를 temp에서 to로 옮김
    hanoi(n - 1, temp, to, from);
}

int main() {
    int n;
    scanf("%d", &n); // 원판 개수 입력

    // 최소 이동 횟수 출력
    printf("%d\n", (int)pow(2, n) - 1);

    // 하노이 탑 이동 출력
    hanoi(n, 1, 3, 2);

    return 0;
}

---

코드 설명

1. 함수 구조

• hanoi 함수:
  • 재귀적으로 원반을 옮기는 과정을 출력합니다.
  • 매개변수:
    • n: 옮길 원반의 개수
    • from: 출발 기둥
    • to: 목표 기둥
    • temp: 보조 기둥
  • 기저 조건: n=1n = 1일 경우, 원반을 한 번만 이동 후 종료.
• main 함수:
  • 사용자로부터 nn을 입력받아 이동 횟수와 과정을 출력합니다.

2. 재귀 호출 순서

1. n−1개의 원반을 보조 기둥으로 이동.
2. 가장 큰 원반을 목표 기둥으로 이동.
3. 보조 기둥의 n−1개의 원반을 목표 기둥으로 이동.

ex) n=3 일 때 동작 과정:

1. A→C: 원반 1 이동.
2. A→B: 원반 2 이동.
3. C→B: 원반 1 이동.
4. A→C: 원반 3 이동.
5. B→A: 원반 1 이동.
6. B→C: 원반 2 이동.
7. A→C: 원반 1 이동.

---

시간 복잡도

하노이 탑의 시간 복잡도는 **O(2^n)**입니다.

• 이동 횟수는 n^2 - 1.
• n이 증가할수록 이동 횟수는 기하급수적으로 증가합니다.

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.