윤성우의 열혈 자료구조를 읽고 복습한 내용입니다.

하노이 타워: The Tower of Hanoi

하노이 타워 문제의 이해

하노이 타워 문제는 앞서 보인 예제들과 달리 재귀적으로 접근하지 않으면 해결이 쉽지 않은 문제이다. 이 문제를 무리 없이 풀거나 이해하면 재귀함수에 어느 정도 익숙해졌다고 볼 수 있기 때문에 의미가 있는 문제이다.

문제의 설명에 대해서는 아래 링크를 참조하기를 바란다.
https://www.acmicpc.net/problem/11729

하노이 타워의 반복패턴 연구

막대를 왼쪽부터 차례대로 1, 2, 3으로 명명하겠다.

4개의 원반을 대상으로 생각해보자.

1. 작은 원반 3개를(맨 아래의 원반을 제외한 나머지 원반을) 1에서 2로 이동
2. 큰 원반(맨 아래의 원반) 1개를 1에서 3으로 이동
3. 작은 원반(B로 옮겨진 원반) 3개를 2에서 3으로 이동

이를 일반화하면 다음과 같다.

1. 작은 원반 n-1개를 1에서 2로 이동
2. 큰 원반 1개를 1에서 3으로 이동
3. 작은 원반 n-1개를 2에서 3으로 이동

이처럼 원반 n개를 이동하는 문제는 원반 n-1개를 이동하는 문제로 세분화되고, 또 원반 n-1개를 이동하는 문제는 원반 n-2개를 이동하는 문제로 세분화된다. 즉, 원반 n개를 이동하는 문제는 결국 원반 1개를 이동하는 매우 쉬운 문제로 세분화되는 것이다.

하노이 타워 문제의 해결

앞에서 일반화했던 내용을 코드로 옮기면 다음과 같다.

const hanoiTowerMove = (n, a, b) => {
  if(n===1){
    return console.log(`원반을 ${a} > ${b} 이동`);
  }
  else {
    hanoiTowerMove(n-1, a, 6-a-b);
    hanoiTowerMove(1, a, b);
    hanoiTowerMove(n-1, 6-a-b, b);
    return;
  }
}

hanoiTowerMove(3,1,3); // 원반 3개를 막대1에서 막대3으로 옮기기

/*
expected output:
원반을 1 > 3 이동
원반을 1 > 2 이동
원반을 3 > 2 이동
원반을 1 > 3 이동
원반을 2 > 1 이동
원반을 2 > 3 이동
원반을 1 > 3 이동
*/

하노이 타워의 문제 해결을 위해서 작성한 코드의 양이 불과 열줄 남짓이란 사실에 주목하자. 이것이 바로 재귀가 지닌 힘이다.