'재귀'에 해당되는 글 1건

  1. 2007.04.25 하노이탑 알고리즘 배워봅시다!! (13)
2007.04.25 01:30
 하노이탑 옮기기 문제

사용자 삽입 이미지

하노이탑 옮기기 문제는 재귀(recursive)를 배울 때 반드시 나오는 문제이다. 또한 네이버 지식인에 가장 많이 질문하는 문제이기도 하다.
이 문제를 처음 보는 사람들을 위해 그 유래와 문제를 살펴보자.

1883년 프랑스 수학자 루카스(Lucas, E.)는 하노이 탑이라고 불려지게 된 유명한 문제를 고안하었다. 문제의 내용은 다음과 같다.

전설에 따르면 천지 창조 시에, 가운데에 작은 구멍이 뚫린 64개의 금으로 된 원판이 하노이의 한 사원에 보관되어 있었다고 한다.

이들 원판은 어느 것도 크기가 같지 않으며, 그림과 같이 작은 원판이 큰 원판 위에 오도록 포개어져, 세 개의 기둥 가운데 한 개에 끼워져 있었다고 한다. 모양이 탑과 비슷하다하여 하노이탑(Hanoi Tower)이라 부른다.

조물주가 사원의 승려에게 명하기를, "크기가 모두 다른 64개의 원판을 하나씩 옮겨서 다른 기둥 위에 원래 상태(작은 원판이 큰 원판 위에 오도록)대로 옮겨 놓되, 옮기는 과정에서 절대로 큰 원판이 작은 원판 위에 놓이지 않도록 하여라. 모든 원판이 옮겨지면 세상은 종말이 올 것이며, 충실한 자는 상을 받을 것이고 불충실한 자는 벌을 받을 것이다"라고 하였다고 한다.

문제가 잘 이해안되는 사람을 위하여 규칙을 다시 정리하면,

  1. 3개의 막대 중 첫번째 막대기(a)에 크기가 모두 다른 64개의 원판이 끼어져 있다.
  2. 64개의 원판은 작은 원판이 큰 원판 위에 있도록 차례대로 포개져 있다.
  3. 이 64개의 원판을 세번째 막대기에(c) 모두 옮겨 놓아야한다. 이때도 작은 원판이 큰 원판 위에 포개져 있어야한다.
  4. 원판을 옮길 때는 반드시 한번에 한개씩 옮길 수 있고 두번째 막대기(b)를 이용할 수 있다.
    예를 들어 첫번째 원판을 두번째 막대기로 옮겨 놓은 후, 두번째 원판을 세번째 막대기로 옮길 수 있다.
  5. 옮기는 과정에서 절대로 큰 원판이 작은 원판 위에 놓이지 않아야한다.
    예를 들어, 첫번째 막대기에 있는 첫번째 원판을 두번째 막대기에로 옮긴 후, 다시 첫번째 막대기에 있는 두번째 원판을 두번째 막대기에 옮기면 안된다. 왜냐하면 이 경우에는 두번째 막대기에 있는 두개의 원반에서, 위의 것이 큰 원반이 되기 때문이다.
문제를 좀더 잘 이해하려면 원판이 2개인 경우와 3개인 경우를 가지고 실제로 한번 해보자. 집에 이런 원판을 가지고 있는 사람은 없을테니, 크기가 다른 3권의 책이나 지우개를 원판 대신 사용하면 된다. 물론 책이나 지우개에 구멍을 뚫을 필요는 없다.


이해를 위해 하노이 탑의 Flow Chart를 추가한다..

사용자 삽입 이미지


문제가 이해되었으면 프로그램을 만들어보자.
이 프로그램을 바로 재귀 프로그램으로 만들지 말고 앞에서 이야기 한 것 처럼 구조화된 프로그램을 만들어 보자. 원판은 64개 대신 3개만 옮기는 것으로 하자. 이때 프로그램의 구조는 다음과 같다.

main() /* n=3으로 move_tower1()을 호출한다. */
|-- move_tower1() /* n=2로 move_tower2()을 호출한다. */
|-- move_tower2() /* n=1로 move_tower3()을 호출한다. */
|-- move_tower3() /* n=1이므로 더 이상 호출하지 않는다. */
이 그림을 가지고, 지금부터 하노이탑 옮기기 프로그램을 앞의 6단계를 따라 해보자.

1단계 - 메인프로그램 만들기

메인프로그램은 다음과 같이 간단하다.

void main() {
void move_tower1(char,char,char,int);
int n; /* 원판의 갯수 */

printf("\n 원판의 갯수를 입력하세요 : ");
scanf("%d", &n); /* 이 문장 대신 n=3;이라고 하는 것이 더 좋다 */
move_tower1('a','b','c',n); /* n개의 원판을 a에서 c 옮김(b 이용) */
}
메인프로그램의 역활은 옮겨야할 원판의 갯수를 입력 받아, 원판을 옮기는 함수(move_tower1)를 한번 호출하고 끝난다.

여기에서 다시 한번 프로세스의 추상화를 상기하자. 즉 원판을 옯기는 프로그램을 만들기가 복잡하고 귀찮으니, 일단 서브프로그램에 넘기고 보자. 다만 서브프로그램에 넘길 때 세개의 막대기(a,b,c)와 원판의 갯수도 함깨 넘겨주자.

2단계 - 1차 서브프로그램 만들기

다음은 1차 서브프로그램(move_tower1() 함수)를 만들어 보자. n개의 원판을 a에서 c로 옮기기 위해 가장 쉬운 방법은 다음과 같다.
  1. 막대기 a에서 맨 아래 한개만 남기고 나머지 (n-1)개는 모두 b에 옮겨 놓는다.
  2. 막대기 a에서 맨 아래의 한개를 c로 옮긴다.
  3. b에 있는 (n-1)개 원판 모두를 c로 옯긴다.
이중 2번은 쉽게 가능하나, 1,3번은 쉽지가 않다.
하지만 문제가 없다. 프로세스 추상화를 이용하면 된다. 즉 서브프로그램에 책임을 떠 넘기면 된다.
그리고 그 서브프로그램(함수)의 이름을 move_tower2()이라고 부르자.


void move_tower1(char a, char b,char c, int n) { /* 3(=n)개의 원판을 a에서 c로 옮김(b를 이용)*/
move_tower2(a,c,b,n-1); /* a에서 맨 아래 하나를 제외한 2(=n-1)개를 a에서 b로 옮김 */
printf("%c 에서 %c로 옯김 \n",a,c); /* a에서 맨 아래 하나를 a에서 c로 옮김 */
move_tower2(b,a,c,n-1); /* b에 있는 2(=n-1)개를 b에서 c로 옮김 */
}
보다시피 2(=n-1)개를 옮기는 과정을 move_tower2()로 넘겨 버렸다.

3단계 - 2차 서브프로그램 만들기

다음 단계로 move_tower2()을 만드는 프로그램을 만들어 보자. 물론 이 프로그램도 로직은 move_tower1()과 똑 같다.


void move_tower2(char a, char b,char c, int n) { /* 2(=n)개의 원판을 a에서 c로 옮김(b를 이용) */
move_tower3(a,c,b,n-1); /* a에서 맨 아래 하나를 제외한 1(=n-1)개를 a에서 b로 옮김 */
printf("%c 에서 %c로 옯김 \n",a,c); /* a에서 맨 아래 하나를 a에서 c로 옮김 */
move_tower3(b,a,c,n-1); /* b에 있는 1(=n-1)개를 b에서 c로 옮김 */
}
이렇게 해서 move_tower2()도 완성하였다.

4단계 - 3차 서브프로그램 만들기

3차 서브프로그램은 n 값이 1이 들어 오게 되므로 루핑의 끝이 된다.

void move_tower3(char a, char b,char c, int n) { /* 1(=n)개의 원판을 a에서 c로 옮김 */
printf("%c 에서 %c로 옯김 \n",a,c);
}
이렇게 해서 move_tower2()도 완성하였다.

5단계 - 프로그램 테스트 하기

여기까지 프로그램을 만든 후 합쳐서 테스트 해보자.

void main() {
void move_tower1(char,char,char,int);
int n; /* 원판의 갯수 */

printf("\n 원판의 갯수를 입력하세요 : ");
scanf("%d", &n);
move_tower1('a','b','c',n); /* n개의 원판을 a에서 c로 옮김(b를 이용) */
}
void move_tower1(char a, char b,char c, int n) { /* 3(=n)개의 원판을 a에서 c로 옮김(b를 이용) */
move_tower2(a,c,b,n-1); /* a에서 맨 아래 하나를 제외한 2(=n-1)개를 a에서 b로 옮김 */
printf("%c 에서 %c로 옯김 \n",a,c); /* a에서 맨아래 하나를 a에서 c로 옮김 */
move_tower2(b,a,c,n-1); /* b에 있는 2(=n-1)개를 b에서 c로 옮김 */
}
void move_tower2(char a, char b,char c, int n) { /* 1(=n)개의 원판을 a에서 c로 옮김(b를 이용) */
move_tower3(a,c,b,n-1); /* a에서 맨 아래 하나를 제외한 n-1개를 a에서 b로 옮김 */
printf("%c 에서 %c로 옯김 \n",a,c); /* a에서 맨 아래 하나를 a에서 c로 옮김 */
move_tower3(b,a,c,n-1); /* b에 있는 1(=n-1)개를 b에서 c로 옮김 */
}
void move_tower3(char a, char b,char c, int n) { /* 1개의 원판을 a에서 c로 옮김 */
printf("%c 에서 %c로 옯김 \n",a,c);
}
일반 구조화된 프로그램과 동일한 형태를 가지고 있기 때문에 쉽게 테스트가 가능하다.

6단계 - 프로그램 조합하기

프로그램의 테스트가 완료되면, move_tower1()과 move_tower3()를 합쳐서 재귀프로그램을 완성하면 된다.

void move_tower(char a, char b,char c, int n) { /* n개의 원판을 a에서 c로 옮김(b를 이용) */
if( n == 1) /* 위의 move_tower3()에 해당 */
printf("%c에서 %c로 옯김\n",a,c); /*원판이 한개면 그냥 a에서 c로 옮기면 됨*/
else { /* 위의 move_tower1()에 해당 */
move_tower(a,c,b,n-1); /*a에서 맨 아래 하나를 제외한 n-1개를 a에서 b로 옮김*/
printf("%c 에서 %c로 옯김 \n",a,c); /* a에서 맨 아래 하나를 a에서 c로 옮김 */
move_tower(b,a,c,n-1); /* b에 있는 n-1개를 b에서 c로 옮김 */
}
}
이것이 최종 완성본이다.

■ 사족(蛇足)

64개의 모든 원판이 옮겨지면 세상은 종말이 온다는 이야기는 64개의 모든 원반을 옮기는데 엄청나게 많은 시간이 걸리기 때문이다. 참고적으로 64개를 모두 옮기기 위해서는 총 (1+2+4+8+16+32+... +2**63)번 옮겨야한다.

[ 출처 : http://blog.naver.com/nawago/90015812409 ]
[ 순서도 출처 : http://hanoi.acroplus.com/300070253 ]

---------------------------------------

락 동생인 혜림이가 물어봐서 찾은 자료

나도 신입생때 C언어 시간에 이걸 풀었었지..

재귀호출에 대한 이해도 필요하지만

하노이탑에 대한 알고리즘을 생각해내는 것도 꽤 문제였는데

이젠 인터넷이 너무 좋아서 이렇게 쉽게 자료를 찾을수있다..

완전 좋은 세상이여~~ ㅎㅎㅎ


덧붙이는 말..

그나저나 위의 최종 소스에서 이렇게 하는것이 더 나은거 아닌가?
이해를 위해서 일부러 저런것인가.. ㅎㅎㅎ


void move_tower(char a, char b,char c, int n) {
if( n > 0) {
move_tower(a,c,b,n-1);
printf("%c 에서 %c로 옯김 \n",a,c);


move_tower(b,a,c,n-1); }
}
Posted by 열라착한앙마

댓글을 달아 주세요

  1. BlogIcon 2007.04.25 10:02 신고  댓글주소  수정/삭제  댓글쓰기

    미로찾기와 더불어 한참 생쑈를 했던기억이 나는구만... ㅎㅎ

  2. BlogIcon 이오니아 2007.04.25 10:38  댓글주소  수정/삭제  댓글쓰기

    저도 학교서 배울때 한참 고민했었던 문제군요..ㅎㅎ 지금도 프로그램을 배우고는 있지만 정말 어려운거 같습니다. 프로그래밍은...OTL

    • BlogIcon 열라착한앙마 2007.04.25 13:10 신고  댓글주소  수정/삭제

      그러게요~
      아무리 공부해도 모를 프로그램같습니다 ㅎㅎ
      한때 저넘의 하노이탑땜에 얼마나 고민했었는지..
      아직도 재귀호출얘기만 나오면 ㄷㄷㄷ;;

  3. BlogIcon 도로케로사랑 2007.05.18 21:46  댓글주소  수정/삭제  댓글쓰기

    제가 영재반에서 64개를 옮기는 시간과 횟수를 계산한 결과(6학년)
    횟수 = 1844경 6744조 737억 955만 1615번을 옮겨야 됩니다...
    걸리는 시간 = 1초에 한번을 옮긴다고 쳤을때...
    5833억년이 걸립니다....
    엄청나죠....

  4. BlogIcon 도로케로사랑 2007.05.18 21:54  댓글주소  수정/삭제  댓글쓰기

    제가 하노이탑 횟수 규칙중 한개를 알려드리죠...
    2개 일때 횟수 = 3
    3개 일때 횟수 = 3+1+3= 7
    4개 일때 횟수 = 7+1+7= 15
    5개 일때 횟수 = 15+1+15= 31
    6개 일때 횟수 = 31+1+31= 63
    7개 일때 횟수 = 63+1+63= 127
    대충 이런 식입니다...
    다른 방법도 많습니다만...

  5. 혜리밍 2008.02.26 15:21  댓글주소  수정/삭제  댓글쓰기

    오빠안녕하세요 ㅋㅋㅋ찾아보러 다시왔어요 하노이탑은 역시 어려워요 잉 ㅜㅜ

    요즘 어떻게지내세요 >_ <

  6. 2009.01.27 23:58  댓글주소  수정/삭제  댓글쓰기

    난 이게 한참을 지나도록 이해가 안갔었는데....

    나만 이해를 못하는 듯 해서 답답해 했던 기억이 나는군하;

  7. BlogIcon ASPIA 2013.04.06 22:24  댓글주소  수정/삭제  댓글쓰기

    소스코드는 아직 안봤지만 플로우차트만으로 프로그램을 만들었더니 제대로 된 프로그램이 안나오더라구요;;;
    혹시 플로우차트가 잘못된거 아닐지..