[JS] 하노이의 탑

* 레퍼런스
Khan Academy - 하노이의 탑

하노이의 탑이란?

하노이의 탑(Tower of Hanoi) 문제는 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원반들이 주어지는데,

다음의 조건을 만족시키면서, 한 기둥에 꽂힌 원반들을 그대로 다른 기둥으로 옮겨서 쌓는 것이 목적이다.

한 번에 한개의 원반만 옮길 수 있다.
이동하는 원반은 세 개의 기둥 중 하나에 반드시 꽂혀야 한다.
가장 위에 있는 원반만 이동할 수 있다.
큰 원반이 작은 원반 위에 있어서는 안 된다.

(A) 기둥에 있는 N개의 원반을 (C) 기둥에 옮기기 위하여,
실행되어야 할 최소 원반 이동 과정을 프로그래밍한다면?

원판이 n개 일 때, 최소 이동 횟수 공식은 (2**n) - 1(번)이다.

예를 들어 한 번의 실수 없이 64개의 원판을 옮기는 데 2^64 - 1 = 18,446,744,073,709,551,615 번을 움직여야 한다. (18경 4,446조 7,407억 3,709만 5,516)

원반 하나를 옮기는 데 1초가 걸린다고 가정하더라도 30층 짜리 하노이 탑을 옮기려면 무려 34년간 먹지도 쉬지도 않고 원반만 옮겨야 한다. (이승찬, 2017)

재귀적으로 생각하기

개인적으로는 시각적인 관찰이 가장 재귀를 이해하는 데 효과적인 것 같아서, 간단하게 그림을 그려보았다.

단계는 2가지가 있다.

1단계 : 기둥 B에 제일 큰 원반을 뺀 나머지 원반들 순서대로 쌓기
2단계 : 남아있는 제일 큰 원반을 목표 기둥인 C에 안착시키기
3단계: 그 위로 다시 제일 큰 원반을 뺀 나머지 원반들 순서대로 쌓기

원반이 1개일 때

가장 작은 문제 (base case)
(1) 1번 원반을 C로 옮긴다. (1단계, 2단계, 3단계 성공)
--> 1개일 때는 1번만 옮기면 끝!

원반이 2개일 때

(1) 1번 원반을 우선 B로 옮긴다.
(2) 2번 원반을 C로 옮긴다. (1단계 성공)
(3) 1번 원반을 C로 옮긴다. (2단계, 3단계 성공)
2개일 때는 3번만 옮기면 끝!

원반이 3개일 때 (횟수 추가)

(1) 1번 원반을 우선 C로 옮긴다.
(2) 2번 원반을 B로 옮긴다.
(3) 1번 원반을 2번 원반 위인 B로 옮긴다. (1단계 성공)
(4) 비어있는 C에 3번 원반을 옮긴다. (2단계 성공)

남아 있는 문제는 B기둥에 순서대로 잘 쌓여있는 1,2번 원반을 C로 옮기는 작은 문제가 되었다.
즉, 위에 <원반이 2개일 때>의 상황이 된 것이다.

재귀다!!!!

사실 1단계 과정도 되돌아보면 <원반이 2개일 때>의 상황이다.
이후의 상황을 다시 그림으로 살펴보면

정리 해보자면 n개의 원반을 옮기기 위해서는

1단계 : 기둥 B에 n-1개의 원반들 순서대로 쌓기 (n-1개의 원반을 쌓는 횟수)
-> n-1개 원반을 쌓으려면...
-> n-2개 원반을 쌓으려면...
...
-> 1개 원반을 쌓으려면... (끝)
2단계 : 남아있는 제일 큰 원반을 목표 기둥인 C에 안착시키기 ( +1번)
3단계: 그 위로 다시 n-1개의 원반들 순서대로 쌓기 (n-1개의 원반을 쌓는 횟수)
-> n-1개 원반을 쌓으려면...
-> n-2개 원반을 쌓으려면...
...
-> 1개 원반을 쌓으려면... (끝)

다소 복잡한 4개일 때 상황으로 다시 한 번 살펴본다.

원반이 4개일 때

4개의 원반을 옮기기 위해서는

1단계 : 기둥 B에 3개의 원반들 순서대로 쌓기
-> 3개 원반 쌓으려면 : 2개 원반 쌓고 + 3번 원반 쌓고 + 다시 2개 원반 쌓는다. (3 + 1 + 3 === 7)
-> 2개 원반 쌓으려면 : 1개 원반 쌓고 + 2번 원반 원하는 위치에 쌓고 + 다시 1개 원반 쌓는다. (1 + 1 + 1 === 3)
-> 1개 원반 쌓으려면 : 1번 이동. (base case)
2단계 : 남아있는 제일 큰 원반을 목표 기둥인 C에 안착시키기 ( +1번)
3단계: 그 위로 다시 3개의 원반들 순서대로 쌓기
-> 3개 원반 쌓으려면 : 2개 원반 쌓고 + 3번 원반 쌓고 + 다시 2개 원반 쌓는다. (3 + 1 + 3 === 7)
-> 2개 원반 쌓으려면 : 1개 원반 쌓고 + 2번 원반 원하는 위치에 쌓고 + 다시 1개 원반 쌓는다. (1 + 1 + 1 === 3)
-> 1개 원반 쌓으려면 : 1번 이동. (base case)
=== 7 + 1 + 7 (15)

** 경험으로 익힌 추가 포인트

제일 처음 1번 원반을 이동할 때, 총 원반의 개수가 짝수개라면, B에 꽂는다. (홀수라면 C)
-> 즉, 현재 총 원반은 4개(짝수) 이므로 처음 시작할 때 1번 원반을 B에 꽂는다.

마지막으로 공식으로 정리해보자면, n개의 원반을 옮기기 위해서는

1단계 : 기둥 B에 n-1개의 원반들 순서대로 쌓기 (n-1개의 원반을 쌓는 횟수 === 2^n-1)
2단계 : 남아있는 제일 큰 원반을 목표 기둥인 C에 안착시키기 ( +1)
3단계: 그 위로 다시 n-1개의 원반들 순서대로 쌓기 (n-1개의 원반을 쌓는 횟수 === 2^n-1)

2^n-1 + 1 + 2^n-1 === 2^n - 1

제일 처음에 살펴본 공식이 나온다.

코드로 나타내보기

코드

function hanoi(disc, a, b, c) {         // n개의 disc를 a에서 c로 옮기는 방법 
  if (disc > 0) {
    hanoi(disc - 1, a, c, b);           // 🟣 n-1개의 disc를 a에서 b로 옮기는 방법 (아래 참고)
    console.log(`Move disc ${disc} from ${a} to ${c}`);
    hanoi(disc - 1, b, a, c);           // 🟡 그 뒤, n-1개의 disc를 b에서 c로 옮기면 된다. (아래 참고)
  }
}

// 끝!!!!!
// 헷갈리니 위의 코드를 부분적으로 뜯어보면,
 function hanoi(disc - 1 , a, c, b) {         // 🟣 n-1개의 disc를 a에서 b로 옮기는 방법
  if (disc > 0) {
    hanoi(disc - 2, a, b, c);           // n-2개의 disc를 a에서 c로 옮기는 방법
    console.log(`Move disc ${disc} from ${a} to ${c}`);
    hanoi(disc - 2, c, a, b);           // 그 뒤, n-2개의 disc를 c에서 b로 옮기면 된다.
  }
}

// function hanoi(disc - 1, b, a, c) {         // 🟡 n-1개의 disc를 b에서 c로 옮기는 방법
  if (disc > 0) {
    hanoi(disc - 2, b, c, a);           // n-2개의 disc를 b에서 a로 옮기고,
    console.log(`Move disc ${disc} from ${a} to ${c}`);
    hanoi(disc - 2, a, b, c);           //그 뒤, n-2개의 disc를 a에서 c로 옮기면 된다.
  }
}
//
//
//
// 반복....

base case : hanoi(1, 'A', 'B', 'C') 디버깅

if (disc > 0) 조건이 참이므로 함수 내부의 코드가 실행된다.
hanoi(disc - 1, a, c, b)를 호출한다. // hanoi(0, a,c,b)
- 0일 때의 조건은 없다. (undefined 리턴)
console.log(Move disc ${disc} from ${a} to ${c}); 코드가 실행된다.
- 이는 disc 값이 1일 때 실행되는 코드이다.
- 따라서, Move disc 1 from 'A' to 'C'가 출력된다.
hanoi(disc - 1, b, a, c)를 호출합니다. // hanoi(0, a,c,b)
- 0일 때의 조건은 없다. (undefined 리턴)
함수가 종료된다.

-> 즉, disc가 1개일 때는 그냥 A에 있는 disc를 C에 꽂으면 끝이다. 그걸 나타낸 것이다.

hanoi(2, 'A', 'B', 'C') 디버깅

[잊지말자! 3단계]
1. 1번 원반을 A에서 B로 옮긴 후에,
2. 2번 원반을 C로 옮겨서
3. 다시 쌓아야 함. (사실, 원반이 2개일 때는 3번 조건 자동으로 충족)

if (disc > 0) 조건이 참이므로 함수 내부의 코드가 실행된다.
hanoi(disc - 1, a, c, b)를 호출한다.
1. 이는 hanoi(1, 'A', 'C', 'B')를 호출하는 것과 동일하다. // (1단계 : 1번 원반을 A에서 B로 옮기기)
2. 이 호출은 disc 값이 1일 때의 base case를 처리한다. // (1번 원반을 A에서 B에 꽂으면 끝이다.)
3. 따라서 Move disc 1 from 'A' to 'B'가 출력된다.
console.log(Move disc ${disc} from ${a} to ${c}); 코드가 실행된다. // (2단계 : 목표 원반 2를 A에서 C로 옮기기)
1. 이는 disc 값이 2일 때 실행되는 코드이다.
2. 따라서, Move disc 2 from 'A' to 'C'가 출력된다.
hanoi(disc - 1, b, a, c)를 호출한다.
1. 이는 hanoi(1, 'B', 'A', 'C')를 호출하는 것과 동일하다. // (3단계 : B로 옮겨둔 1번 원반을 C로 옮기기)
2. 이 호출은 disc 값이 1일 때의 base case를 처리한다. // (1번 원반을 B에서 C에 꽂으면 끝이다.)
3. 따라서 Move disc 1 from 'B' to 'C'가 출력된다.
함수가 종료된다.

결과적으로, hanoi(2, 'A', 'B', 'C')는 다음과 같은 순서로 원판을 옮기며 최소한의 이동 횟수로 하노이의 탑 문제를 해결한다.

Move disc 1 from A to B
Move disc 2 from A to C
Move disc 1 from B to C

간단한 hanoi(3, 'A', 'B', 'C') 디버깅

이제 이해가 되었으니, 정리할 겸 마지막 간단한 디버깅을 해본다.

[잊지말자! 3단계]
1. 2번 원반을 A에서 B로 차곡차곡 옮긴 후에, (1번 원반이 위에, 2번 원반이 아래에)
2. 3번 원반을 목표지점 C로 옮겨서
3. B로 예쁘게 쌓아둔 2번 원반을 C에 다시 차곡차곡 쌓아야 함.

hanoi(2, a, c, b)를 호출한다. // (1단계 : 2번 원반을 A에서 B로 차례대로 옮기기)
console.log(Move disc ${3} from ${a} to ${c}); 코드가 실행된다. // (2단계 : 목표 원반 3을 A에서 C로 옮기기)
hanoi(2, b, a, c)를 호출한다. // (3단계 : B로 옮겨둔 2번 원반을 C로 옮기기)

결과 확인

honoi(3, 'A', 'B', 'C')디버깅

프로그래머스 코딩테스트

[입출력 예]
- 입력 : solution(2) // 총 2개의 원반을 옮기는 방법
- 출력 : [ [1,2], [1,3], [2,3] ]
// [1번 기둥 제일 위에 있는 원반(1)을 2번 기둥에 옮기고],
// [1번 기둥 제일 위에 있는 원반(2)을 3번 기둥에 옮기고],
// [2번 기둥 제일 위에 있는 원반(1)을 3번에 옮긴다.]

가서 풀어보기
아래의 접은 글은 해결 방법 및 구현 코드이다.

해결 방법 : solution 함수 안에 재귀함수를 넣으면 되겠다.

코드

function solution(n) {

    const answer = [];
    
    const hanoi = (n, start, mid, end) => {
    if (n > 0) {
      hanoi(n-1, start, end, mid)
      answer.push([start,end])
      hanoi(n-1, mid, start, end)
    }
  }
  
  hanoi(n, 1, 2, 3)
  return answer;
}

728x90

저작자표시

'FE > JavaScript' 카테고리의 다른 글

[JS] 꼬리재귀 (0)	2023.04.27
[JS] 재귀를 이용하여 Tree UI 구현하기 (0)	2023.04.12
[JS] JSON.stringify 재귀를 이용하여 직접 구현하기 (0)	2023.04.12
[JS] JSON 개요 (JavaScript Object Notation) (0)	2023.04.12
[JS] 재귀 (0)	2023.04.11

개발해도유