[C / JAVA] 하노이탑 알고리즘 구현하기

하노이탑은 재귀호출을 이용한 가장 대표적인 예입니다.

 이렇게 세개의 기둥이 있고 두가지의 조건을 만족시키면서 다른 기둥으로 원판을 옮기는 게임입니다.

<조건>

1. 한 번에 하나의 원판만 옮길 수 있다.

2. 큰 원판이 작은 원판 위에 올 수 없다.

 n개의 원판이 있으면 2ⁿ -1의 이동으로 원판을 모두 옮길 수 있습니다.

알고리즘

- 기둥1에 있는 n개의 원판을 기둥2를 이용하여 기둥3으로 옮기는 알고리즘

(편의상 기둥 3개를 기둥1, 기둥2, 기둥3이라고 하겠습니다)

1. 기둥1에서 n-1개의 원판을 기둥3를 이용하여 기둥2으로 옮긴다.

2. 기둥1에서 남은1개의 원판을 기둥3으로 옮긴다.

3. 기둥2에서 n-1개의 원판을 기둥1을 이용하여 기둥3으로 옮긴다.

이걸 이제 코드상에서 구현을 해보도록 하죠.

저 알고리즘을 그대로 코드로 옮겨보도록 하겠습니다. - JAVA 사용

1.     public void Hanoi(int n, char from, char by, char to){
2.        
3.         if(n == 1){
4.             Move(from,to,n);
5.         } else{           
6.             Hanoi(n-1,from,to,by);
7.             Move(from,to,n);
8.             Hanoi(n-1,by,from,to);           
9.         }       
10.     }
11.    
12.     public void Move(char a, char b, int n){
13.         System.out.println(n + "이동" + a + "->" + b);       
14.     }

<설명>

1. Hanoi라는 함수를 하나 만든다. (원판의 갯수, 기둥1, 기둥2, 기둥3)

2. 3~4줄은 종료조건임. 즉, 원판이 n-1개가 다 이동을하면 하나의 원판만 남게 되니까 재귀를 종료하기 위한 종료 조건이 됨.

3. 5~8줄이 위의 알고리즘을 그대로 옮긴 것임. 

 - 기둥1에서 n-1개의 원판을 기둥3을 이용하여 기둥2로 옮긴다. -> Hanoi(n-1,from,to,by);

 - 기둥1에서 남은 1개의 원판을 기둥3으로 옮긴다. -> Move(from,to,n);

 - 기둥2에서 n-1개의 원판을 기둥1을 이용하여 기둥3으로 옮긴다. -> Hanoi(n-1,by,from,to);

글 읽어보시면 그대로 코드가 작성이 된 것을 보실 수 있으실 겁니다. from이 기준 기둥 by가 이용하는 기둥 to가 최종 목적지 기둥이 됩니다. 

하노이탑은 재귀호출이 어떻게 이루어지는지 알 수 있으면 쉽게 해결할 수 있습니다.

실행결과

따봉버튼한번씩부탁드립니다♥