[JS] 3Level / 연습문제 / 하노이의 탑

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/12946

프로그래머스

 

문제 풀이 방법

이 문제는 모 부트캠프 코테를 보며 기억에 남은 문제중 한개이다.

 

하노이의 탑 문제는 기본적으로 재귀 함수를 사용해 풀어야 하는 문제이며, 나는 이걸 이해하기 힘들었다.

문제에서 중요한 것은 제일 큰 원판을 제외한 나머지 원판들은 목적지가 아닌 경유지에 모두 있어야 하고, 제일 큰 원판을 옮긴 뒤 나머지 원판들도 경유지를 거쳐 목적지로 옮겨야 한다는 것이다.

이 때, 재귀 함수가 2번 사용된다.

1. 제일 큰 원판을 제외한 나머지 원판들을 경유지로 옮길 때
2. 제일 큰 원판을 옮긴뒤 나머지 원판들을 목적지로 옮길 때

 

완성된 코드

const solution = (n) => {
    let answer = [];
    const hanoi = (n, from, to, via) => {
        if(n === 1) answer.push([from, to]);
        else{
            hanoi(n-1, from, via, to);
            answer.push([from, to]);
            hanoi(n-1, via, to, from);
        }
    }
    hanoi(n, 1, 3, 2);
    return answer;
}

 

참고 링크

https://velog.io/@jewon119/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B8%B0%EC%B4%88-%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98-%ED%83%91Tower-of-Hanoi

알고리즘 기초 - 하노이의 탑(Tower of Hanoi)