하노이 탑

하노이 탑

각기 다른 크기의 원판들과 판 위에 세워진 세개의 막대로 구성된다. 원판의 순서를 유지한 채 마지막 막대로 옮기는 문제이다. 작은 원판 위에 큰 원판이 올 수 없다.

이러한 과정을 거쳐 간다.

코드

function solution(n) {
    const answer = [];
    
    const hanoi = (num, start, mid, end) => {
        
        if(num === 1){
            answer.push([start, end]);
            return;
        }
      	// 목적지를 가운데로 설정하고 재귀를 쭉 들어감
        hanoi(num - 1, start, end, mid);
        answer.push([start,end]);
      	// 앞 재귀가 끝나고 시작을 가운데, 목적지를 마지막으로하고 재귀가 들어감
        hanoi(num - 1, mid, start, end);
    }
    hanoi(n, 1,2,3);
    return answer;
}

n 개의 원판을 옮기는 함수이다.

n개의 원판을 1번 기둥에서 3번 기둥으로 옮기기 위해서는
n-1개의 원판을 1번에서 2번 기둥으로 옮기고, 남아있는 원판을 1번에서 3번으로 옮긴다. 그리고 2번으로 옮겼던 n-1개의 원반을 3번으로 옮긴다.

원판이 하나만 남는다면, 시작점에서 끝점으로 옮기고 재귀를 끝낸다.

하노이 탑 원판이 n개 일 때, 총 이동횟수는

2^n - 1 이된다.