한빛출판네트워크

저자: 김대곤

지난 번 기사에는 Induction에 대한 이야기를 다루었다면, 이번 기사에서는 유명한 논리게임 중에 하나인 Tower of Hanoi를 통해서 조금 실감나게 Induction이 어떻게 프로그램에 사용되는지 살펴보도록 하자. 먼저 이 게임의 규칙을 살펴보자.



이 게임의 목적은 1번 위치에 놓인 링을 모두 3번 위치로 옮기는 것이다. 한 번에 하나의 링만 움직일 수 있고, 위에 링이 있으면 움직일 수 없다. 단순히 옮기는 것이 아니라, 큰 링은 작은 링보다 아래에 있어야 한다. 즉 형태를 그대로 보존하는 것이다. 옮기는 과정에서도 이 규칙은 지켜져야 한다. 즉, 큰 링은 작은 링 위로 옮길 수 없다. 일반적 경우에는 1번 위치에서 3번으로 옮길 수 있다. 하지만 1번(3번) 위치에서 3번(1번) 위치로 갈 때 반드시 2번을 지나야 한다는 제한을 하나 더 두자. 즉, 한 번에 한 칸 밖에 움직일 수 없다. 이제 링들을 옮기는 프로그램을 만든다고 가정해 보자.

복잡해 보일지 모르지만, Induction으로 간단히 해결할 수 있다. 먼저 다음의 쉬운 문제를 생각해 보자.

만약 링이 하나만 있다고 하자. 아마 초등학생도 할 수 있을 것이다. 1번 위치에서 2번 위치로 움직이고, 다시 2번 위치에서 3번 위치로 움직인다.

이제 N 개의 링이 1번 위치에 있다고 하자. 당신은 N 개 링을 1번 위치에서 3번 위치로 옮기는 법을 모른다. 하지만 당신은 N - 1 개는 어떻게 옮기는지 알고 있는 것처럼 가정하자. 이제 다시 그림으로 돌아가 보자. 가장 큰 링은 빈 칸으로만 갈 수 있다. 왜냐하면, 다른 모든 링이 자기 자신보다 작기 때문이다. 자기 위에 있는 모든 링이 3번 위치에 가야 가장 큰 링이 2번 위치로 갈 수 있다. 당신은 N – 1 개의 링을 1번 위치에서 3번 위치로 옮기는 방법을 알고 있다. 그러면 옮겨보자. 이제 가장 큰 링은 1번 위치에 있고, 다른 링들은 모두 3번 위치에 있다. 가장 큰 링을 2번 위치로 옮겨 보자. 가장 큰 링이 3번 위치로 가기 위해서는 3번이 있는 모든 링이 1번 위치로 가야한다. 당신은 N – 1 개의 링을 옮기는 방법을 알고 있다. 옮기자. 이제는 가장 큰 링이 2번 위치에 있고, 다른 링들은 1번 위치에 있다. 이제 가장 큰 링을 3번 위치로 옮기자. 이제 남은 일은 1번 위치에 있는 N – 1 개의 링을 다시 3번 위치로 옮기는 것이다. 당신을 어떻게 하는지 알고 있고 있다. 모른다고?

당신은 알고 있다. 어쩌면 몰라도 상관 없을지 모른다. 아니 생각하기 시작하면 머리만 아플 것이다. Induction에서는 두 가지를 필요로 한다. 베이스 케이스와 Inductive step이 그것이다. 당신은 링 하나를 움직이는 법(베이스 케이스)와 N – 1 개의 링을 움직일 수 있다는 가정 하에서 N 개의 링을 움직일 수 있다.(Inductive step)

정리해 보면,
링이 하나일 때는 그 링을 1번에서 2번으로 2번에서 3번으로 옮긴다.
링이 N 개일 때는 N – 1 개의 링을 3번으로 옮기고, 가장 큰 링을 2번 위치로 옮긴다. 다시 3번 위치에 있는 N – 1 개의 링을 1번 위치로 옮기고, 가장 큰 링을 3번 위치로 옮긴다. 남은 일은 1번 위치에 있는 N – 1 개의 링을 3 번 위치로 옮기는 것이다.

이제 이것을 프로그램으로 옮겨보자.


/*
 * Created on 2005. 2. 2.
 * @author DaeGon Kim
 *
 */
 
public class Honai {

              public static int moveN = 0;

              public static void main(String[] args) {

                            /* check number of input arguments */
                            if ( args.length != 2 ) {
                                          System.out.println("Usage : java Honai [#disks] [start]");
                                          System.exit(0);
                            }

                            /* convert input and check the value */
                            int n     = Integer.parseInt(args[0]);
                            int start = Integer.parseInt(args[1]);

                            if ( n < 1 ) {
                                          System.out.println("Number of disk should be greater than 1");
                                          System.exit(0);
                            }


                            if ( start == 1 ) {
                                /* call recursive method */
moves(1, n, start, 3);
                            } else if ( start == 3 ) {
                                /* call recursive method */
moves(1, n, start, 1);
                            } else {
                                          System.out.println("start should be 1 or 3");
                                          System.exit(0);
                            }

                            System.out.println("The number of moves is " + moveN);


              }

              public static void moves(int start, int end, int source, int dest) {
                            int n = end - start + 1;

        /* base case */
                            if ( n == 1 ) {
                                          System.out.println("Move disk["+ start + "] from peg[" + 
             source + "] to peg[" + 2 + "]");
                                                        moveN++;
                                          System.out.println("Move disk["+ start + "] from peg[" + 
                                                        2 + "] to peg[" + dest + "]");
                                                        moveN++;
        /* inductive step */
                            } else {
                                          moves(start, end-1, source, dest);
                                          System.out.println("Move disk["+ end + "] from peg[" + 
                                                        source + "] to peg[" + 2 + "]");
                                                        moveN++;
                                          moves(start, end-1, dest, source);
                                          System.out.println("Move disk["+ end + "] from peg[" + 
                                                        2 + "] to peg[" + dest + "]");
                                                        moveN++;
                                          moves(start, end-1, source, dest);
                            }
              }

}


위 코드를 보지 않더라도 간단하게 프로그램할 수 있을 것이다. 필자의 생각했던 것보다 Induction을 사용하여 해결할 수 있는 문제가 아주 많았다. 단지 사용할 수 있는지가 잘 안 보였을 뿐이다. 인터넷 검색 엔진으로 Tower of Hanoi로 검색하면 쉽게 여러 가지 사이트를 찾을 수 있고, 자바 애플릿 프로그램을 쉽게 구할 수도 있다. 이것은 아마도 Induction을 이해하면 이 문제가 쉽기 때문일 것이다. 독자들에게도 이 문제가 쉽게 여겨지길 바라며 글을 마치고자 한다.