[Algorithm] 하노이의 탑 알고리즘 Javascript 구현하기

 

 

 

재귀 알고리즘?

 

[Algorithm] 재귀 알고리즘이란 recursion algorithm

 

[Algorithm] Javascript Recursion Memory Leak 재귀 함수와 메모리 사용량 분석 알아보기

 

 

하노이의 탑 알고리즘

 

하노이의 탑은 대표적인 재귀 알고리즘 문제다. 베트남의 지명을 딴 문제지만 베트남이랑은 아무 관련이 없다. 하노이의 탑은 원판을 다른 장소로 이동하면서 최종적으로 모든 원판을 특정 장소에 위치시키는 문제다.

여담으로 하노이의 탑에는 전설이 붙어 있다. 고대 인도 베나레스의 사원에서는 다이아몬드로 이뤄진 3개의 기둥이 있다. 기둥에 끼울 수 있게 준비된 63개의 황금 원판이 꽂혀 있다. 원판은 아래쪽으로 갈수록 크기가 커지는 구조로 되어 있다. 한번에 한번씩만 원판을 다른 기둥으로 옮길 수 있고 크기가 큰 원판은 작은 원판위에 올라갈 수 없다.

이 규칙으로 모든 원판을 다른 기둥으로 옮기는 시점에 탑은 무너지고 세상의 종말이 찾아온다고 한다.

 

하노이의 탑 원리

 

하노이의 탑을 다른 기둥으로 모두 옮기는데 필요한 횟수는 (2^n - 1)회가 필요하다. 즉 3개의 원판이면 7번, 4개의 원판이면 15번 원판을 옮겨야 하고, 전설에서 처럼 63개의 원판을 옮기기 위해서는 (9.223372037×10¹⁸ -1) 회가 필요하다. 참고로 63개 원판을 옮기는 횟수는 9백 2십 2경 3천 3백 7십 2조 번 가량이다. 

문제 : 

주어진 N개의 원판을 3번째 기둥으로 옮기는 작업. 한번에 한개의 원판을 이동할 수 있고 크기가 큰 원판은 작은 원판위에 올라갈 수 없음. 원판을 이동시킨 횟수와 이동 히스토리를 출력하라.

 

풀이 : 

횟수 : 2^n -1

 

재귀 로직 : 

function hanoi(원판의 갯수, from_ , to_, via_){}

 

탈출 조건은 이동할 원판이 1개 밖에 남지 않은 상황이다. 재귀 로직은 피보나치 수열과 같이 2번의 재귀 함수를 호출하면서 각 원판을 다른 기둥으로 옮기게 된다. 탈출 조건 충족 시 새로운 배열에 이동 히스토리를 기록하고, 모든 로직이 완성된 후 한번에 출력한다.

재귀 로직은 콜 스택을 사용하기 때문에 Tail Call 알고리즘을 사용하는게 좋지만, 하노이의 탑 문제에서 Tail Call을 작성하는 알고리즘은 찾아보기 힘들다. 원판이 이동할 수 있는 장소는 2곳이 존재하기 때문에 분기가 되면서 재귀 로직이 작동한다. 

 

소스코드 : 

 

/*
  Date : 2022년 5월 13일
  문제 : 백준 1914 하노이의 탑
  알고리즘 : 재귀 알고리즘
  작성자 : About-Tech
*/

const readline = require('readline');

const r = readline.createInterface({
    input:process.stdin,
    output:process.stdout,
})


r.on('line', (item)=>{
        const input = item.split(' ');

        const i = Number(input[0]);

        if(i<=20){
            let resArr = [];

            const hanoi = (n, from_, to_, via_) => {
                if(n === 1) resArr.push(`${from_} ${to_}`) 
                else{
                    hanoi(n-1, from_, via_, to_);
                    resArr.push(`${from_} ${to_}`) 
                    hanoi(n-1, via_, to_, from_);
                }
            }
            console.log(BigInt(Math.pow(2, i)-1).toString());

            hanoi(i, 1, 3, 2);
            
            console.log(resArr.join("\n"))
        }
    
    r.close();
})

r.on('close', ()=>{
    process.exit();
})

 

원판이 5인 경우 원판을 이동하는 횟수는 총 (2^5-1 = 31)번이 작동한다. 

입력값 : 5
31
1 3
1 2
3 2
1 3
2 1
2 3
1 3
1 2
3 2
3 1
2 1
3 2
1 3
1 2
3 2
1 3
2 1
2 3
1 3
2 1
3 2
3 1
2 1
2 3
1 3
1 2
3 2
1 3
2 1
2 3
1 3