프로그래머스 [Lv. 2] 하노이의 탑 {언어 : JavaScript}

문제 링크

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

프로그래머스

정답 코드

function solution(n) {
    const answer = [];
    const hanoiT = (number, fromT, toT, assistT) => {
        if (number == 1) {
            answer.push([fromT, toT])
            return
        }  
        hanoiT(number-1, fromT, assistT, toT)
        answer.push([fromT, toT])
        hanoiT(number-1, assistT, toT, fromT)
    }
    hanoiT(n, 1, 3, 2)
    return answer;
}

풀이 방법

1. 함수를 만든다.
   1. fromT가 처음 탑이 쌓여있는 곳이자 옮기고 싶은 탑
   2. toT가 이제 쌓을 탑이자 옮길 최종 탑
   3. assistT가 처음 탑에서 옮길 탑으로 돌을 옮길 때 도와줄 탑
   4. 즉, 최종으로 fromT에서 toT으로 옮길 때 assistT을 이용한다는 의미
2. number를 1을 줄여서 돌 하나를 옮겼다고 계산한다.
3. fromT에서 assistT으로 돌을 옮기는데 여기서 toT을 이용한다.
4. 실행 과정을 살펴보면

function solution(n) {
    const answer = [];
    const hanoiT = (number, fromT, toT, assistT) => {
        console.log("start", number)
        if (number == 1) {
            console.log("final", number, fromT, toT)
            answer.push([fromT, toT])
            return
        }  
        hanoiT(number-1, fromT, assistT, toT)
        console.log("next", number, fromT, toT)
        answer.push([fromT, toT])
        hanoiT(number-1, assistT, toT, fromT)
    }
    hanoiT(n, 1, 3, 2)
    return answer;
}

n이 3일 경우 [[1, 3], [1, 2], [3, 2], [1, 3], [2, 1], [2, 3], [1, 3]] start 3 start 2 start 1 final 1 1 3 next 2 1 2 start 1 final 1 3 2 next 3 1 3 start 2 start 1 final 1 2 1 next 2 2 3 start 1 final 1 1 3 start가 함수가 실행되는 시점이다.

느낀점

• 하노이의 탑은 여전히 어렵다.
• 계속해서 다시 풀어보는 방법 밖에는 없는 것 같다.