안녕하세요, 매일 코딩입니다.
이번에는 자바를 이용해서 하노이 탑을 만들어 봅시다.
하노이 탑은 작은 원반이 위에 있고 큰 원반이 아래에 있는 탑을 말합니다.
이해를 돕기 위해 그림으로 설명합니다.
이렇게 1번 기둥에 있는 원반을 3번 기둥으로 옮길 수 있습니다.
이번에는 하노이 탑을 코드로 해볼게요.
출력값: 원반의 개수는?: 3 탑 [1]을 1 기둥에서 3 기둥으로 옮긴 탑 [2]을 1 기둥에서 2 기둥으로 옮긴 탑 [1]을 3 기둥에서 3 기둥으로 옮긴 탑 [2]을 1 기둥에서 3 기둥으로 옮긴 탑 [1]을 2 기둥에서 1 기둥으로 옮긴 탑 [2]을 옮긴 탑 [2]을 2 기둥에서 1 기둥으로 옮긴 탑 [2]을 2 기둥으로 옮긴 탑 [2]을 2
코드설명1. 먼저 여기에서 Hanoi(3, 1, 3)라고 가정합니다.
2. Hanoi(3, 1, 3)에서 Num은 1보다 크기 때문에 먼저 if(Num > 1){Hanoi(Num – 1, x, 6 – x – y)}~에 들어갑니다.
그러면 Hanoi (Num – 1, x, 6 – x – y)는 Hanoi (2, 1, 2)가 됩니다.
3. Hanoi (2, 1, 2)는 다시 Hanoi (1, 1, 3)가 됩니다.
여기서 Num > 1보다 커야하기 때문에 처음에 (1, 1, 3)이 출력이 됩니다.
그 후(2, 1, 2)가 출력이 됩니다.
4. 이번엔 (2,1,2) 아래 if문으로 들어갑니다.
(1, 3, 2)을 갖게 됩니다.
5. Hanoi(3 1, 3)는 위에 있는 if문에서 이미 사용되었습니다 그 후 (3, 1, 3)을 출력한 후 아래의 if문으로 들어갑니다.
6. (3, 1, 3)이 (2, 2, 3)이 되고, 이 (2, 2, 3)은 위에 있는 if문에 들어갑니다.
(1, 2, 1) 을 출력합니다.
7. 그 다음에 (2,2,3) 을 출력하고 마지막으로 (2,2,3) 가 아래의 if 문에 들어갑니다.
그렇게 되고, 마지막으로(1, 1, 3) 순서가 출력됩니다.
이번에는 하노이 탑 알고리즘에 대해서 설명을 드렸는데요
감사합니다~