[알고리즘] 하노이의 탑 알고리즘 이해 돕기 | 재귀함수 과정

 

 

 

하노이의 탑 알고리즘 이해 돕기

 

하노이의 탑은 크게 어렵지 않고 간단해서 초보자도 설명을 차근히 읽어본다면 이해하기 어렵지 않다. 하지만 내 기준에서 '코드를 이렇게 설명하면 더 좋은 이해가 될 것 같다'라는 생각에 이 글을 올린다. 

 

 

 

[하노이의 탑 알고리즘의 기본적 도해]

 

하노이의 탑

시작기둥1에서 목적기둥3으로 n개의 원반을 모두 옮기는 단계를 보여주는 흔한 그림이다. 

 

위 그림에서 볼 수 있듯이,

하노이의 탑을 이루는 n개의 원반은 '맨 아래원반'과 '나머지 원반묶음'이라는 두 분류로 바라봐야 한다.

 

---

---

 

그리고 나서 n-1원반묶음을 또 분리하여 '맨밑원반'과 'n-2원반묶음'으로 나누는 방식을 통해서,  원반묶음의 이동을 연쇄적으로, 재귀적으로 바라볼 수 있다. 

 

 

 

---

   그럼 이제 슬슬 코드로 확인해보자

 

재귀함수의 대표적 사례인 하노이의 탑의 코드를 제대로 이해하려면 두 가지 사실을 새겨둬야 한다

 

- 기둥은 딱 3개다! (시작기둥, 목적기둥, 남는기둥)

- n개의 원반의 구성은 '맨 아래 원반'과 '나머지 n-1개의 원반묶음'이다. 

 

---

---

 

 

그럼 본격적으로 시작해보자. 

다음의 순서로 설명하겠다. 

 

 

 

다음은 흔하게 찾아볼 수 있는 하노이의 탑 알고리즘이다.

재귀호출이 2번 이루어지고 있다. 한번 보자!

// Java로 작성했지만 알고리즘은 당연히 동일

static void move(int n, int x, int y) {
  if (n>1)
    move(n-1, x, 6-x-y);     // 재귀호출 1
  
  // x에 있던 원반 n을 목표기둥 y로 옮김
  System.out.println("원반"+n+"을 " + x + "기둥에서 " + y + "기둥으로 옮김");
  
  if (n>1)
    move(n-1, 6-x-y, y);     // 재귀호출 2
  }
}

 

 

 

과정을 하나씩 끊어서 확인해보자. 

   하노이의 탑 알고리즘 이해하기

 

▶ 6-x-y의 의미에 대한 이해

 

- 기둥은 3개라는 전제가 중요하다. 기둥1, 기둥2, 기둥3으로 구분할 것이다.

인자로 들어가는 x는 n개의 원반이 존재하는 시작기둥, y는 최종적으로 n개의 모든 원반을 이동시킬 기둥이다.

 

6 = x기둥번호 + y기둥번호 + 남은기둥번호

6 - x기둥번호 - y기둥번호 = 남은기둥번호

 

그래서 6-x-y라는 변수는 '남은 기둥의 번호'를 의미한다. 

(사실 이것만 알면 다 이해한 거다)

 

 

남은 기둥(6-x-y)를 따져야 하는 이유도 알아야 하노이의 탑을 시원하게 이해할 수 있다. 

 

>> ㅁ, ㅂ, ㅇ라는 기둥 세개가 있다고 해보자. 

n개의 원반을 ㅁ에서 ㅂ으로 옮기고 싶다. 

그러면 n-1원반묶음을 ㅁ,ㅂ말고 ㅇ에 뭉텅이로 올려두고, 맨아래에 있던 원반n을 목적기둥인 ㅂ에 가장 먼저 올려두어야 한다. 그리고 나서 남은기둥 ㅇ에 있던 n-1원반묶음 뭉텅이를 목적기둥인 ㅂ에 올려두면 모든 원반을 목적기둥 ㅂ으로 옮기기 성공이다. 

 

 

다음 설명을 보면 남은기둥을 왜 따지는지 더 잘 알게 될 것이다. 

 

 

즉, 세 개의 기둥 중, 

 

- 시작기둥(x)은 그냥 시작기둥이고 

- 목적기둥(y)에는 맨밑원반을 둬야하고

- 남는기둥에는 n-1원반묶음을 올려두어야 한다

 

그래서 남는기둥 6-x-y을 따지는 것이다. 

 

 

---

 

▶ 재귀호출 1에 대한 이해

 

// 재귀호출 1
move(n-1, x, 6-x-y);

첫번째 인자인 n-1은 가장 아래에 있는 원반n을 제외한 n-1개의 원반묶음을 의미한다.

 

 

 

 

▶ 원반 n을 x기둥에서 y기둥으로 옮겼다는 print 부분

 

// x에 있던 원반 n을 목표기둥 y로 옮김
System.out.println("원반"+n+"을 " + x + "기둥에서 " + y + "기둥으로 옮김");

 

 

 

▶ 재귀호출 2에 대한 이해

 

// 재귀호출 2
move(n-1, 6-x-y, y);

 

역시 첫번째 인자 n-1은 맨아래원반 n을 제외한 나머지 n-1원반묶음을 의미한다. 

6-x-y는 x와 y가 아닌 셋 중 나머지 기둥을 의미하고, y는 최종 목적 기둥을 의미한다.

 

 

 

---

그림에서 봤던 간단한 세 단계가 각각 '재귀호출1', 'print', '재귀호출2'에 해당함을 명확하게 확인할 수 있었다. 인자로 들어가는 n-1, x, y, 6-x-y들의 의미만 정확히 느낀다면 딱히 어렵지 않은 알고리즘이다. 

 

 

다시 한번 강조하고 마친다. 

 

- 시작기둥(x)은 그냥 시작기둥이고

- 목적기둥(y)에는 맨밑원반을 둬야하고

- 남는기둥에는 n-1원반묶음을 올려두어야 한다