하노이 타워 / 재귀

내가 재귀를 처음 배울 당시 재귀의 활용성과 유용함을 인지하지 못한 채로 학습하였다.

 

재귀의 특성을 잘 활용하기만 한다면, 매우 어렵고 복잡해 보이는 문제도 간결한 코드를 만들 수 있다는 것을 체감 하기 전까지 그랬었다.

 

하노이 타워는 그러한 재귀의 유용성을 직접 피부로 느낄 수 있게 되었다.

 

 

본격적으로 하노이 타워가 어떤 문제인지 살펴보자

 

'하나의 막대에 쌓여 있는 원반을 다른 하나의 원반에 그대로 옮기는 방법'에 관한 것이다.

 

3개의 막대 A, B, C가 주어져있을때

 

A에 꽂혀있는 모든 각각 크기가 다른 원반을 막대 C로 옮겨야 한다. 이때 제약조건이 있다.

 

 

1. 원반은 한번에 하나씩만 옮길 수 있다. 2. 작은 원반위에 큰 원반이 올 수 없다.

 

글로 설명하면 이해가 쉽지 않으니 그림을 첨부 하였다.

 

하노이의 탑 (출처 : 위키백과)

재귀를 이용하려면 먼저 문제에 반복적으로 적용되는 어떠한 방법을 찾아 내야 한다.

 

모든 탑을 C막대에 옮기려면 가장 큰 원반이 가장 아래쪽에 위치하여야 한다.

 

이를 단계로 나누어서 체계화 하여보자

 

하노이 탑 출처 : 자료구조 - 윤성우

일단 그러기 위해서는 1,2,3 번 원반을 B막대에 모두 옮기고

 

그후 4번 원반을 C막대에 옮긴다.

그후 다시 남은 1, 2, 3번 원반을 C막대에 옮긴다.

 

하지만 여기서 이렇게 질문 할 수 있다.

 

처음 1,2,3번 원반을 B 원반에 옮기는 과정과, 막대 B에서 C로 옮기는 과정은 어떻게 할 것인가?

하지만 앞선 1번 2번 3번 막대를 옮기는 과정도 결국 원리는 정확히 같다.

 

다시한번 글로 짧게 설명해 보면

 

1. 작은 원반 3개를 A -> B

2. 가장 큰 원반 A->C

3. B에 위치한 작은원반을 B->C

 

이를 일반화 한다면, 작은 원반을 구하는 과정도 세분화 할 수 있고 이에 대한 관계식을 정리 할 수 있다.

 

총 n개의 원반이 있다면

1. n-1까지의 원반을 A->B

2. n원반을 A->C

3. n-1의 원반을 B->C

 

여기서 생각해보자 재귀함수는 탈출조건 (basecase)가 꼭 필요하다. 이문제에서는 탈출조건이 어떤 경우인가?

 

가장 마지막 1원반이 남았을 때 그 원반을 옮기기만 하면 모두 옮긴 것이다. 

 

그렇기 때문에 base case는 n==1 일때이다.

 

이관계식을 가지고 재귀함수를 직접 구현하여보자.

 

이번에는 교제 및 다른 참고자료 없이 혼자 직접 구현을 시도하여 보았다.

 

#include<stdio.h>

void Hanoi (int n, char from, char by, char to){

  // from 옮길 원반의 시작 막대

  // by 도착지를 가기 위해 거치는 막대

  // to 옮길 원반의 막대

  if (n==1) // base case

  {

    printf("1번 원반 %c->%c로 이동\n",from, to);

  }

  else{

    Hanoi(n-1,from,to,by); // 작은원반 n-1개를 모두 B로 이동 = 1단계

    printf("%d번 원반 %c->%c로 이동\n",n,from,to); // 큰원반 n을 A->C이동

    Hanoi(n-1,by,from,to); // // n-1개의 원반 B->C이동

  }

}

int main(){

  // 옮길 원반의 갯수

  int n = 3;

  Hanoi(n,'a','b','c');

  return 0;

}

하노이 탑 함수 실행 결과

 

재귀 함수를 처음 접했을 때 조금 이런식으로 코드를 써도 잘 동작할까? 라는 느낌이 강했다.

 

그래서 인지 피부로 와닿지 않고 그저 어렵게만 느껴졌다.

 

하지만 함수가 호출되는 중 다시 함수가 호출될 때 수 많은 재호출이 이루어지고 결국 n=1이 되어 base case 까지 도달하지 못한다면 다시 호출되는 그 원리를 머릿속에서 파악하려고 노력했다.

 

 

 

하노이의 탑을 공부하며 느낀점

 

Hanoi(n-1,from,to,by);

함수 안에서 처음으로 만나는 간결하게 한줄로 쓰여있는  재호출 코드는 매우 간결하지만 이 리턴값을 얻기위해 엄청난 과정을 거친다는 것을 많이 느끼는 것이 중요하다고 생각된다.

 

재귀호출을 사용한다는 것은 복잡하고 어려운 코드를 간결하게 짤 수 있지만, 조금만 늘어나도 컴퓨터가 감당해야할 계산량이 매우 늘어나기 때문에 컴퓨터 입장에서 효율적이라고 보기 어렵다.

 

즉 직접 우리가 서비스할 코드에 사용된다면 최적화 문제로 고생해야 할 것이다.

 

DP(Dynamic Program)는 이러한 문제점을 획기적으로 해결할 수 있다.

 

이러한 재귀적 특성을 몰랐을 때의 DP를 무작정 접해보았는데 무엇이 좋고 왜 쓰는가를 모르니 그저 나는 교제를 따라갈 뿐이였다.

 

(물론 DP는 재귀를 이용한 DFS(깊이우선탐색)알고리즘 말고 다른 방법도 있지만)