하노이탑 [11729]

문제

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

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

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

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

입력

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

접근

하위 문제 정의: n-1개의 원판을 출발지(A)에서 보조 막대(B)로 옮긴다.

가장 큰 원판 이동: 출발지 막대(A)의 가장 큰 원판을 목표 막대(C)로 옮긴다.

하위 문제 재귀 해결: n-1개의 원판을 보조 막대(B)에서 목표 막대(C)로 옮긴다.

코드

const readline = require('readline');

// readline 인터페이스를 만듭니다.
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

// 질문을 던지고 답변을 받습니다.
let input=[];
rl.on('line', function (line) {
    input.push(line);
}).on('close', function () {
    
    let N = parseInt(input[0]);
    let H =[];

    function Hanoi (plate,start,end){

        if(plate==1){
            H.push(start+" "+end);
            return 
        }else{
            Hanoi(plate-1,start, 6 - start - end );
            H.push(start+" "+end);
            Hanoi(plate-1 ,6 - start - end , end );
        }
    }

    Hanoi(N,1,3);
    
    let output = `${H.length}\n` + H.join('\n');
    console.log(output);
    process.exit();
});

복잡도 분석

• 시간 복잡도: O(2^n) - 각 원판마다 두 번의 재귀 호출이 발생.
• 공간 복잡도: O(n)- 재귀 호출의 깊이가 n에 비례.

교훈

• 재귀는 수열의 점화식과 비슷한 느낌이다.
• 가장 간단한 케이스부터 생각을 하면서 확장해보자.