문제 풀이

🔖 문제

하노이 탑 이해하기

📚 공식 설명 블로그

하노이 탑 알고리즘은 기둥1에 있는 N개의 원반을 기둥2를 이용해서 기둥3으로 옮기는 알고리즘이다.

이 알고리즘의 메너니즘은 아래와 같이 동작한다.

Step 1

기둥1에서 N-1개의 원반을 기둥3을 이용하여 기둥2로 옮긴다.

Step 2

기둥1에서 1개의 원반을 기둥3으로 옮긴다.

Step 3

기둥2에서 N-1개의 원반을 기둥1을 이용하여 기둥3으로 옮긴다.

하노이 탑 구현하기

구현은 위 Step을 하나하나 작성하면 된다.

public static void hanoi(int n, int from, int by, int to) {

    if (n == 1) {
        move(from, to);
        return;
    }

    hanoi(n - 1, from, to, by);
    move(from, to);
    hanoi(n - 1, by, from, to);
}