[알고리즘-PS(재귀)] Java로 하노이 탑 알고리즘 재귀적으로 구현하기 :: Hanoi Tower Algorithm Java Code by recursion

하노이 탑은 정말 유명한 퍼즐이다.
하노이 탑에 대해서 자세히 알고싶다면 하노이탑 위키 에서 자세히 읽어보는 것도 재밌을 것 같다.

하노이 탑을 간단하게 설명하자면

세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다.

게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다.

 

조건

• 한 번에 하나의 원판만 옮길 수 있다.
• 큰 원판이 작은 원판 위에 있어서는 안 된다. -> 항상 작은 원반이 위에 있어야 한다.

하노이 탑의 원판을 모두 옮기려면 (2^n - 1)의 경우가 필요하다. 하지만 우리는 재귀 호출에 대해서 능하기 때문에 빠르고 간단하게 풀어보자.

문제 분석

일단 하노이 탑 문제를 풀기 위해서 문제를 분석해보자.

 

하노이 탑은 3개의 기둥으로 나눌 수 있다.

시작 기둥

시작 기둥은 N개의 원판이 있을 때 옮기기를 시작하는 기둥이 된다.

보조 기둥

보조 기둥은 N개의 원판이 목표 기둥으로 옮겨질 때 Buffer로써 사용되는 기둥이다.

목표 기둥

목표 기둥은 N개의 원판이 옮겨져야 하는 목표 기둥이 된다.

---

 

그리고 순서대로 한 번 찾아보자.

1 개의 원판이 있을 때

한 개의 원판이 있다면 시작 기둥에 하나가 있을 것이고, 단지 시작 기둥에서 목표 기둥으로 옮기기만 하면 끝이다.

 

이 것을 코드화 시켜본다면 다음과 같다.

void hanoi(원판의 수, 시작 기둥, 보조 기둥, 목표 기둥) {
    if (원판의 수 == 1) {
        System.out.println(시작 기둥 + "->" + 목표 기둥);
        return;
    }
}

2 개의 원판이 있을 때

두 개의 원판이 있다면 시작 기둥에 두 개가 있는 상태이다. 그럼 다음과 같은 과정을 거쳐 보자.

 

1. 첫 번째 원판을 보조 기둥으로 옮긴다. -> 가장 작은 원판을 보조 기둥으로 옮긴다.
2. 나머지 원반을 목표 기둥으로 옮긴다. -> 그럼 자연스럽게 시작 기둥에는 제일 큰 원판만 남게 된다.
3. 보조 기둥에 있는 원판을 목표 기둥으로 옮긴다.

 

 

여기서 핵심은 가장 큰 원반을 제외한 나머지 원반을 보조 원반으로 옮겨야 한다는 것이다.

또 이 것을 코드화 시켜보자.

hanoi(원판의 수 - 1, 시작 기둥, 보조 기둥, 목표 기둥)

즉 맨 마지막 원판을 제외한 나머지 모든 기둥을 시작 기둥 -> 보조 기둥으로 옮기는 과정이라고 생각하면 된다.

 

그리고 원판의 수가 1이 된다면 시작 기둥에 있는 원판을 목표 기둥으로 옮기는 일을 수행해준다.

System.out.println(시작 기둥 + "->" + 목표 기둥);

여기 까지 수행한다면 그림의 3 번째 모양과 같아질 것이다.

그럼 여기서 생각을 해보자.

목표 기둥에 있는 가장 큰 원판보다 큰 원판이 존재해서 하노이의 규칙을 깨는 경우가 있을까??

정답은 No다.

그럼 가장 큰 원판을 제외한 나머지 원판에게 같은 논리를 적용하면 된다.

 

그리고 다음과 같은 상태가 될 것이다.

이제 이 상태로 재귀적으로 수행한다면 된다.

 

원판이 n개 일 때

원판이 n개일 때는 앞의 로직을 그대로 따라준다면 걱정 없이 해결될 것이다.

 

그것을 코드로 표현해본다면

void hanoi(원판의 수, 시작, 목표, 보조) {
    if (원판의 수 == 1) {
        System.out.println(시작 + "->" + 목표);
        return;
    }
    hanoi(원판의 수 - 1, 시작, 보조, 목표);
    System.out.println(시작 + "->" + 목표);
    hanoi(원판의 수 -1, 보조, 목표, 시작);
}