하노이 탑이 이해가지 않는 나에게...

<하노이 탑 메소드>

static void move(int no, int x, int y) {
	if (no > 1)
    	move(no - 1, x, 6 - x - y);
        
    System.out.printf("원반 [%d]을(를) %d번 기둥에서 %d번 기둥으로 옮김\n",no,x,y);
        
    if (no > 1)
        move(no-1,6-x-y,y);  
}

원반이 4개인 경우

위 메소드에 따라 재귀호출을 해가며 완성한 원반 4개짜리 하노이 탑의 모습이다. 순서대로 표현하면 다음과 같다.

원반이 옮겨지는 순서&nbsp;이것도 검색트리의 한 종류였는데 까먹었다..

하노이의 탑의 근본적인 해결책은 맨 아래원반을 제외하고 나머지 원반들이 중간 기둥에 모인 후, 맨 아래원반을 세번째 기둥으로 옮기고 다시 중간 기둥에 있는 원반들을 세번째 기둥에 옮기는 것이다. 위 그림에서 큰 틀로 본다면 다음과 같다.

원반 4개일 때 하노이의 탑 근본적인 해결책으로 묶어서 봄

원반이 4개일 경우 위 3개의 원반들을 묶어서 1개라고 가정한다면 원반이 2개일 경우로 생각하고 실행하면 된다. 그럴려고 보니 1개라고 생각했던 놈이 알고보니 3개였고 이를 크기순으로 차곡차곡 다시 쌓아서 가운데 기둥으로 보내기 위해서 위에서 했던 로직을 다시 반복해야 하는 것이다. 이처럼 점점 그룹이 작아지면서 로직을 반복해서 실행하다보면 원반 각각 하나의 움직임이 보인다.