하노이의 탑

하노이 탑 알고리즘은 재귀함수의 대표적인 알고리즘 중 하나

 

동작방식

https://shoark7.github.io/programming/algorithm/tower-of-hanoi

세 개의 기둥 중 하나의 기둥에 지름이 서로 다른 여러 개의 원판들이 크기순으로 쌓여 있음

 

https://shoark7.github.io/programming/algorithm/tower-of-hanoi

이 원판들을 다른 기둥으로 옮기는 과정

 

규칙

• 한 번에 하나의 원판만 옮길 수 있음
• 큰 원판 위에 작은 원판을 올릴 수 없음
• 중간 단계로 사용할 수 있는 보조 기둥을 활용할 수 있음

 

동작방식 예시

• n-1개의 원판을 보조 기둥으로 옮김
• 가장 큰 원판을 목표 기둥으로 옮김
• 보조 기둥에 있는 n-1개의 원판을 목표 기둥으로 옮김

https://shoark7.github.io/programming/algorithm/tower-of-hanoi

 

하노이 예시

• 구현코드

public class HanoiTower {
    public static void main(String[] args) {
        int num = 3;
        
        solveHanoi(num, 'A', 'B', 'C');
    }
    
    public static void solveHanoi(int num, char start, char to, char via) {
        if (n == 1) {
            System.out.println(num + "번 원반을 "+ start +"에서 " + to + "로 이동");
            return;
        }
        
        solveHanoi(n - 1, start, via, to);
        System.out.println(num + "번 원반을 "+ start +"에서 " + to + "로 이동");
        solveHanoi(n - 1, via, to, start);
    }
}

 

• 출력문

1번 원반을 A에서 C로 이동
2번 원반을 A에서 B로 이동
1번 원반을 C에서 B로 이동
3번 원반을 A에서 C로 이동
1번 원반을 B에서 A로 이동
2번 원반을 B에서 C로 이동
1번 원반을 A에서 C로 이동

 

참고자료 https://shoark7.github.io/programming/algorithm/tower-of-hanoi