#AIL_23.12.06 // Programmers_하노이의 탑

## AIL_ 하노이의 탑

***문제 설명
하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.

1. 한 번에 하나의 원판만 옮길 수 있습니다.
2. 큰 원판이 작은 원판 위에 있어서는 안됩니다.

하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.

***제한사항
n은 15이하의 자연수 입니다.

***입출력 예

n	result
2	[[1,2],[1,3],[2,3]]

***입출력 예 설명
입출력 예 #1_다음과 같이 옮길 수 있습니다.

---

## solution.JavaScript

1. 문제의 접근 방식

1)  원반이 1개일 때, 해당 원반을 출발지에서 목적지로 직접 옮깁니다. 이것이 재귀 알고리즘에서의 기본 단계입니다.

 

2)  1개가 아닌 여러 개의 원반을 옮기기 위해서는 다음과 같은 단계를 반복합니다.  

2-1. n-1개의 원반을 경유지로 이동합니다. (출발지 -> 경유지)

2-2.  남은 1개의 원반을 목적지로 이동합니다. (출발지 -> 목적지)

2-3. 경유지에 있는 n-1개의 원반을 목적지로 이동합니다. (경유지 -> 목적지)

 

3) 함수 호출의 순서는 다음과 같습니다.

3-1. hanoi(n-1, 출발지, 목적지, 경유지): n-1개의 원반을 경유지로 이동.

3-2. answer.push([출발지, 목적지]): 가장 큰 원반을 목적지로 이동.

3-3. hanoi(n-1, 경유지, 출발지, 목적지): 경유지에 있는 작은 원반들을 목적지로 이동.

---

2. 문제풀이

// n => 이동할 원반의 갯수 
// a => 원반이 위치한 기둥 번호 
// b => 목적지 기둥 번호
// c => 경유할 기둥

 function solution(n) {
   const answer = [];

   function hanoi(n, a, b, c) {
     // 원반이 1개일 경우 목적지로 이동
     if (n === 1) {
       answer.push([a, c]);
       return;
     }

     // n-1개의 원반을 경유지로 이동
     hanoi(n - 1, a, c, b);

     // 가장 큰 원반을 목적지로 이동
     answer.push([a, c]);

     // n-1개의 원반을 경유지에서 목적지로 이동
     hanoi(n - 1, b, a, c);
   }

   hanoi(n, 1, 2, 3);
   return answer;
 }
/*
 테스트 1
입력값 〉	2
기댓값 〉	[[1, 2], [1, 3], [2, 3]]
실행 결과 〉	테스트를 통과하였습니다.
*/

 

1. ` solution ` 함수는 하노이 탑 문제를 해결하기 위한 메인 함수입니다. 이동 경로를 저장할 배열 answer를 초기화합니다.

 

2. `hanoi` 함수는 재귀적으로 호출되며, 주어진 기둥 번호 a에서 시작하여 목적지 기둥 번호 c로 최소한의 움직임으로 원반을 이동합니다.

 

3. `n === 1`인 경우, 즉 원반이 1개일 때는 해당 원반을 목적지로 직접 이동하고 이동 경로를 answer 배열에 추가합니다.

 

4. 그렇지 않은 경우, 큰 원반을 제외한 나머지 원반들을 경유지로 이동하고, 가장 큰 원반을 목적지로 이동한 뒤, 다시 나머지 원반들을 목적지로 이동합니다.

 

5. `hanoi` 함수를 호출하여 하노이 탑 문제를 해결하고, 최종적으로 이동 경로가 담긴 `answer` 배열을 반환합니다.

---

3. 다른사람의 문제풀이 및 접근방식 분석

  function solution(n, from = 1, by = 2, to = 3) {
     return (n===1) ? [[from, to]] : [...solution(n-1, from, to, by), ...solution(1, from, by, to), ...solution(n-1, by, from, to)]
 }
/*
 테스트 1
입력값 〉	2
기댓값 〉	[[1, 2], [1, 3], [2, 3]]
실행 결과 〉	테스트를 통과하였습니다.
*/

/*
function solution(n, from = 1, by = 2, to = 3) {
  return (n === 1) 
    ? [[from, to]] // 원반이 1개일 경우, 직접 목적지로 이동
    : [
        ...solution(n - 1, from, to, by),     // n-1개의 원반을 경유지로 이동
        ...solution(1, from, by, to),          // 가장 큰 원반을 목적지로 이동
        ...solution(n - 1, by, from, to)       // n-1개의 원반을 경유지에서 목적지로 이동
      ];
}

*/

 

 

1) n === 1) ? [[from, to]] : [...solution(n-1, from, to, by), ...solution(1, from, by, to), ...solution(n-1, by, from, to)] 원반이 1개일 경우에는 바로 목적지로 이동한 경로를 반환합니다. 그렇지 않은 경우에는 다음 세 가지 경로를 결합한 배열을 반환합니다.

1-1. n-1개의 원반을 경유지로 이동한 경로

1-2. 가장 큰 원반을 목적지로 이동한 경로

1-3. n-1개의 원반을 경유지에서 목적지로 이동한 경로

2. 귀 호출을 통한 해결

2-1. 재귀 호출을 통해 작은 문제로 나누어 해결하고, 이를 조합하여 전체 문제를 해결합니다.
2-2. 각 호출은 원반이 1개일 때까지 반복되며, 각 호출이 반환하는 경로들을 합쳐 최종적인 이동 경로를 구합니다.

---

#  재귀함수란? 

재귀 함수는 함수가 자기 자신을 호출하는 특성을 가진 함수를 말합니다. 즉, 문제를 해결하기 위해 동일한 함수를 여러 번 호출하여 문제를 해결하는 방법입니다.

---

#  재귀함수 특징

1. 자기 자신을 호출하는 형태

 함수 내에서 자기 자신을 호출하는 형태를 갖추고 있어야 합니다.

 

2. 탈출 조건 (Base Case)

무한히 반복되지 않도록 종료 조건이 필요합니다. 재귀 호출이 계속되다가 특정 조건에 도달하면 더 이상 호출하지 않고 종료하는 부분이 필요합니다.

---

#  재귀함수 사용방법

function factorial(n) {
  // Base Case: 탈출 조건
  if (n === 0 || n === 1) {
    return 1;
  } else {
    // Recursive Case: 자기 자신을 호출하면서 문제를 작은 부분으로 분할
    return n * factorial(n - 1);
  }
}

// 예제 사용
console.log(factorial(5)); // 5! = 5 * 4 * 3 * 2 * 1 = 120

---

#  재귀함수 주의사항

1. Base Case 누락 주의

 재귀 함수에서 가장 중요한 부분은 Base Case를 정확하게 설정하는 것입니다. Base Case를 설정하지 않거나 잘못 설정하면 무한 재귀에 빠질 수 있습니다.

2. 스택 오버플로우 주의

 재귀 함수를 사용할 때, 함수 호출이 계속 쌓이면서 스택 메모리를 소비하게 됩니다. 일정 깊이 이상의 재귀 호출이 발생하면 스택 오버플로우가 발생할 수 있습니다.

---

#  재귀함수 장단점

***장점

1. .코드의 간결성

일부 문제는 재귀를 사용하면 코드가 간결해지며 이해하기 쉬워집니다.

2. 복잡한 문제 해결

어떤 문제는 재귀를 사용해 해결하기가 편리합니다.

***단점

1. 성능

일부 경우에는 반복문에 비해 성능이 떨어질 수 있습니다.

2. 메모리 사용

많은 재귀 호출이 스택에 쌓이면 메모리 사용량이 늘어날 수 있습니다.