[백준/C언어] 11729번 - 하노이 탑 이동 순서

백준 웹사이트 "11729번 - 하노이 탑 이동 순서" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

11729번: 하노이 탑 이동 순서

---

소스 코드

#include <stdio.h>
 
int hanoi(int n, int start, int end, int tag);
int other_rod(int start, int end);
 
int main(void){
    int N;
    scanf("%d", &N);
 
    int count = hanoi(N, 1, 3, 0);
    printf("%d\n", count);
    hanoi(N, 1, 3, 1);
}
 
int hanoi(int n, int start, int end, int tag){
    //base case
    if(n==1){
        if(tag==1){
            printf("%d %d\n", start, end);
        }
        return 1;
    }
    //recursive case
    else{
        int other = other_rod(start, end);
        int count = hanoi(n-1, start, other, tag);
        count += hanoi(1, start, end, tag);
        count += hanoi(n-1, other, end, tag);
        return count;
    }
}
 
int other_rod(int start, int end){
    if(start!=1 && end!=1)
        return 1;
    else if(start!=2 && end!=2)
        return 2;
    else
        return 3;
}

---

문제 풀이

  대표적인 재귀 문제 중 하나인 하노이 탑 문제입니다. 이번 문제에서는 'hanoi'와 'other_rod' 두 개의 함수를 사용하였는데, 그중 'other_rod'는 시작 장대와 목표 장대가 아닌 다른 장대를 구하는 간단한 함수입니다. 시작 장대를 1, 목표 장대를 3으로 고정할 수 없는 이유가 재귀를 하다보면 계속해서 시작, 목표 장대가 변하기 때문입니다. 시작, 목표 장대가 아닌 나머지 장대를 쉽게 구하기 위해 'other_rod' 함수를 사용합니다.

  이 문제의 핵심은 'hanoi' 재귀함수입니다. 'n'는 원판의 개수이고, 'start'와 'end'는 각각 시작 장대와 목표 장대입니다. 마지막으로 'tag'는 Line 19 printf의 실행 여부인데, 이에 대해서는 추후에 설명하겠습니다. 이전 10872번 문제에서, 재귀 함수의 두 가지 조건으로 'Base Case'와 'Recursive Case'이 있음을 언급했습니다. 'hanoi' 함수에서 Base Case는 Line 17 ~ 22로, n이 1일 때입니다. 원판이 1개일 때는 시작 장대에서 목표 장대로, 한 번의 이동만 하면 되기 때문에 1을 반환하고, printf를 통해 이동을 기록합니다. Recursive Case는 Line 24 ~ 30으로, 2개 이상의 원판이 있을 때에 해당됩니다. n개의 원판이 있으면 위 n-1개의 원판을 start → other 장대로 옮긴 뒤, 밑의 원판을 start → end 장대로 옮기고, 다시 n-1개의 원판을 other → end 장대로 옮깁니다. 이때 hanoi 함수를 실행할 때마다 반환되는 값은 이동 횟수이므로, 이를 합한 값이 총 이동 횟수가 됩니다.

  'tag' 파라미터를 사용하지 않아도 결과는 똑같습니다. 다만, 총 이동 횟수는 모든 재귀가 끝난 후에 구해지는 것이기 때문에, '첫째 줄에 옮긴 횟수 K를 출력한다. 두 번째 줄부터 수행 과정을 출력한다' 문제 조건을 수행할 수 없게 됩니다. 따라서 재귀 함수를 두 번 실행하여, 처음에는 수행 과정이 출력되지 않도록 tag=0으로 설정하여 막고, 두 번째에는 tag=1로 설정하여 수행 과정이 출력되도록 합니다. 사실 N개의 원판을 옮기면, 총 이동 횟수는 항상 $2^N-1$이므로, 이를 따로 계산하여 처음에 출력하고, 재귀 함수를 한 번만 실행해도 됩니다. 하지만 이런 공식을 모르고 있을 경우, 순수한 코딩만으로 나타내는 방법도 알고 있으면 좋다고 생각합니다.

  아래는 'Base Case'와 'Recursive Case'에 대한 백준 웹사이트 "10872번 - 팩토리얼" 문제풀이 링크입니다.

[백준/C언어] 10872번 - 팩토리얼