하노이의 탑이란 무엇인가?

▏목적

 

      ◦ 하노이의 탑 알고리즘 이해하기

      ◦ 하노이의 탑 알고리즘 JAVA로 구현하기

 

 

 

 

▏시작하는 말

 

오늘은 하노이의 탑 을 공부해봤다. 이름이 새로워서 내가 모르는 것인 줄 알았으나 어릴적 다들 한 번씩은 해봤던 놀이였다. 가지고 놀았던 게임을 제대로 분석하고 공부해서 코드로 구현해보니 더 재미있고 신기했다. 그럼 이제 그 하노이의 탑을 설명해보도록 하겠다. 

 

 

 

 

▏하노이의 탑

 

하노이의 탑 규칙은 큰 원반이 아래, 작은 원반이 위로가게 해서 원반을 3개의 기둥사이에서 옮기는 것 이다.

 

원반은 1번에 1개씩만 옮길 수 있고, 모든 원반은 크기가 다르며 큰 원반이 작은 원반 위로 가서는 안되는 규칙이 있다. 또 최소한의 이동으로 목표 기둥으로 옮겨야 한다.

 

 

 

 

▏원리

 

왼쪽 기둥부터 편의상 1, 2, 3번 기둥이라고 부르도록 하겠다.

 

1. 우선 제일 큰 원반을 제외한 나머지를 그룹으로 생각한다.

   그 그룹을 2번기둥으로 모두 옮기고 제일 큰 원반을 3번 기둥으로 옮긴다.

 

2.  그룹에서 제일 큰 원반을 제외한 나머지를 새로운 그룹으로 묶는다.

   그 그룹을 1번 기둥으로 옮긴 후 제일 큰 원반을 3번기둥에 쌓는다.

 

3.  위 과정을 반복하는 것인데, 한 번만 더 설명하자면

   그룹이었던 원반들 중 제일 큰 원반을 제외해 새로운 그룹을 다시 만든다. 

   그 후 2번 기둥으로 옮긴 후 제일 큰 원반을 3번 기둥에 옮기면 되는 것 이다.

 

 

이런식으로 제일 큰 원반을 제외한 나머지를 그룹으로 만들어 현재 있는 기둥과 3번 기둥을 제외한 나머지로 옮기고, 제일 큰 원반을 3번 기둥으로 옮기는 식으로 하면 된다. 

 

 

 

 

▏예제 1

 

원반 3개를 옮기는 방법을 설명해보겠다.

위에서 설명했듯이 제일 큰 원반인 3 을 제외한 나머지를 그룹으로 묶는다. 이 그룹을 기둥 2번 으로 옮기고 원반 3을 기둥 3번으로 옮긴다. 그리고 1,2번 그룹을 3번 기둥으로 옮기면 되는데 이역시 같은 원리로 하면 되는데 다음 그림에서 설명하겠다.

 

 

 

원반 1, 2의 위치만 2번 기둥에서 1번 기둥으로 바뀌어 있을 뿐이지 3번 기둥으로 옮기는 원리는 같다.

 

원반 1을 한 그룹으로 생각한 후 자신기둥인 1번, 옮겨야 할 3번 기둥을 제외한 나머지(2번 기둥)로 옮긴 후 제일 큰 원반(2)를 3번 기둥으로 옮긴다. 그리고 남은 그룹을 3번 기둥으로 옮기면 끝난다.

 

 

 

 

▏예제 2

 

마지막으로 원반이 4개일 때를 설명하고 하노이의 탑 설명은 끝내도록 하겠다.

 

이것도 마찬가지로 제일 큰 원반(4)을 제외한 나머지를 그룹을 묶고 이 그룹을 2번 기둥으로 옮긴다. 원반 4를 3번 기둥으로 옮기고 남은 그룹을 위에서 설명한 방식대로 3번 기둥으로 옮기면 된다.

 

 

 

 

 

▏JAVA 구현

public class Hanoi {

	public class Hanoi{
    	int count = 0 ;
    	int hanoiFunction(int n, int first, int second, int third) { 
        	if(n==1){
            	System.out.println(first+"->"+third); 
            	count++;
            	return count;
        	}
        	hanoiFunction(n-1, first, third, second);  
	        System.out.println(first+"->"+third); 
        	count++; 
        	hanoiFunction(n-1, second, first, third); 
        
	    	return count;
    	} 
    }
    
    public static void main(String[] args) {

        Hanoi hanoi = new Hanoi();
        
//      hanoi.hanoiFunction(3, 1, 2, 3);
        System.out.println("총 옮긴 횟수: "+myHanoi.hanoiFunction(3, 1, 2, 3)); // 2의 n제곱 - 1 = 옮긴 횟수
    }
}

 

 

 

 

▏참고자료

 

https://brunch.co.kr/@younggiseo/139

https://shlee0882.tistory.com/64