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

Posted by 돼지로운생활
2016. 12. 23. 16:42 개발자의 길/알고리즘

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



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

<조건>

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

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


 n개의 원판이 있으면 2n -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가 최종 목적지 기둥이 됩니다. 


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


실행결과


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



유용한 IT정보 / 전자제품 리뷰
포털에서 MilkyeWay를 검색해주세요👍
유용한 정보였다면 ❤️ 클릭 부탁드려요 😄

이 댓글을 비밀 댓글로