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

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

코드

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

void hanoi(int n, int from, int temp, int to);

int main(void) {
    int n = 0;

    scanf("%d", &n); //원판의 개수 N 입력

    printf("%d\n", (int) pow(2, n) - 1); //원판을 옮긴 횟수 : 2^n - 1
    hanoi(n, 1, 2, 3); //hanoi 함수 호출
}

void hanoi(int n, int from, int temp, int to) { //풀이 확인
    if(n == 1) {
        printf("%d %d\n", from, to);
    }
    else {
        hanoi(n - 1, from, to, temp);
        printf("%d %d\n", from, to);
        hanoi(n - 1, temp, from, to);
    }
}

풀이 (n = 3 일 때 기준)

원판이 n개이고 시작 기둥이 1, 임시 기둥이 2, 도착 기둥이 3일 때
시작 기둥에서 임시 기둥 -> 맨 밑 원판을 도착 기둥으로 -> 임시 기둥에서 도착 기둥 순서로 진행해야 한다

1번째로 from에서 temp로 가는 hanoi 함수를 재귀함수로 호출한다
이 때, 제일 작은 원판부터 옮겨야 하므로 n == 1 이라는 기저 조건을 통해 n개 생성된 스레드 중
(1) n이 1인 스레드에서 먼저 제일 작은 원판을 시작 기둥에서 도착 기둥으로 옮겨준 후 스레드가 종료된다
(2) n이 2인 스레드에선 hanoi 함수를 호출해서 처리했으니(=n이 1인 경우) printf를 통해 시작 기둥에서 임시 기둥으로 옮겨주고
(3) 2번째 hanoi 함수를 호출해 n이 1이 되어 도착 기둥에서 임시 기둥으로 옮겨준 후 스레드가 종료된다
(4) 맨 처음 스레드에선 1번째 hanoi 함수를 처리했으므로 printf를 통해 시작 기둥에서 도착 기둥으로 옮겨준 후 2번째 hanoi 함수 호출
(5) 2번째 hanoi 함수로 인해 생긴 스레드에서 n이 2기 때문에 1번째 hanoi를 새로운 스레드에 호출해 n이 1이 되어 임시 기둥에서 시작 기둥으로 옮긴다
(6) 1번째 hanoi 함수를 처리했으니 printf를 통해 임시 기둥에서 도착 기둥으로 옮긴다
(7) 2번째 hanoi 함수를 호출해 n이 1이 되어 시작 기둥에서 도착 기둥으로 옮긴 후 종료된다

hanoi 재귀함수의 흐름도(n = 3 일 때)

 

아직도 from temp to의 로직은 잘 모르겠지만 재귀함수를 이해하는덴 도움이 된 문제였다

재귀함수 == 다중 스레드라고 생각했던게 이해하는데 정말 도움이 됐었다