알고리즘 - 하노이 탑

하노이 탑

---

재귀 알고리즘의 대표적인 문제로 하노이 탑 문제가 있다.

 

문제를 설명해 보자면 1번 기둥에 있는 원반들을 3번 기둥으로 옮겨야 되는데 여기서 조건이 하나 있다.

길이가 짧은 원반 위에 길이가 긴 원반을 둘 수 없다는 조건이 있는데 해당 조건을 고려하며 문제를 풀어보자.

 

public void hanoiTest(int from, int mid, int to, int value) {
    if (value >= 1) {
        hanoiTest(from, to, mid, value - 1);
        System.out.printf("%d번 원반을 %d번에서 %d번으로 옮겼다.\n", value, from, to);
        hanoiTest(mid, from, to, value - 1);
    }
}

코드는 재귀를 통해서 구현하게 되는데 3줄밖에 되지 않는 저 코드를 이해하는데 너무 어려웠다.

이해가 가지 않아서 하나 씩 자세히 들여다보았다.

먼저 처음 매개변수로 넘어오는 값을 보면 from = 1, mid = 2, to = 3, value = 3이다.

from, mid, to는 각 기둥을 표시하는 것이고 value는 원반의 개수를 의미하는 것이다.

먼저 if문이 false가 될 때까지 재귀 함수가 실행되는데 마지막 코드에서 from = 1, mid = 3, to = 2, value = 0으로 hanoiTest 메서드를 실행하게 되면 false가 나온다.

그러면 그전으로 돌아가 value가 1일 때로 돌아가게 되고 1번 원반을 1번 기둥에서 3번 기둥으로 옮기게 된다.

그다음 hanoiTest(mid, from, to, value - 1) 메서드가 실행되게 된다.

위의 코드와 같이 hanoiTest(2, 1, 3, 1 - 1)이 실행되고 if문에서 false 값이 나오게 되므로 그전 단계로 돌아가게 된다.

그 전 단계에서는 from = 1, mid = 3, to = 2, value = 2이므로 1번 기둥에서 2번 기둥으로 2번 원반을 옮기게 된다.

옮긴 후 hanoiTest(mid, from, to, value - 1) 메서드를 실행하게 되는데 여기서 mid = 3, from = 1, to = 2, value = 2가 된다.

 

위의 설명을 코드에 적용시켜 풀어보면 사진과 같이 된다. hanoiTest(3, 2, 1, 1 - 1)을 실행하게 되면 if문이 false가 되기 때문에 다시 돌아오게 되고 3번 기둥에서 2번 기둥으로 1번 원반을 옮기게 된다.

위와 같은 일련의 과정을 반복하게 되면 아래와 같은 결과값이 나오게 된다.

역시 어떤 로직이든지 이해가 잘 안 되면 하나씩 값을 대입해 보면서 풀어보면 이해가 쉽게 되는 것 같다.