하노이의 탑(feat. 부셔버려)

하노이의 탑

재귀함수 문제의 대명사.

0) 귀납법

1) 1일때 맞다. => 종료조건 (수렴) 2) n일때, n+1도 맞다. => 작업부분(메서드)

1) 종료 조건

n=1일때, 1번째 원반을 시작기둥에서 목표기둥으로 옮긴다.

2) 메서드 부분

1. n-1번째까지의 원반을 시작기둥에서 목표기둥이 아닌 제 3의 기둥으로 옮긴다. (n-1개를 동일하게 하노이)
2. n번째 원반을 시작기둥에서 목표기둥으로 옮긴다. (1개 옮기는 것)
3. n-1번째까지의 원반을 제 3의 기둥에서 목표기둥으로 옮긴다. (n-1개를 동일하게 하노이)

3) 코드

static void moveDisk(int disk_num, int start_stick, int final_stick) {
    System.out.printf("%d번 원반을 %d에서 %d로 옮기세요.\n", disk_num, start_stick, final_stick);
}

// n은 원반 개수, start_stick은 시작점 위치,
// final_stick은 목적점 위치, 6-start_stick-final_stick은 나머지 한개 기둥의 위치
static void hanoi(int n, int start_stick, int final_stick) {
    if(n==1) {
        moveDisk(1, start_stick, final_stick);
        return;
    }
    hanoi(n-1, start_stick, 6-start_stick-final_stick);
    moveDisk(n, start_stick, final_stick);
    hanoi(n-1, 6-start_stick-final_stick, final_stick);
}

---

마지막 수정일시: 2022-05-23 18:30