[Programmers] 하노이의 탑

문제 : https://programmers.co.kr/learn/courses/30/lessons/12946

---

오랜만에 풀어보는 하노이의 탑. 

재귀로 풀었다.

A -> C로 N개의 원판을 옮긴다고 해보자.

가장 아래에 있는 원판을 제외한 N-1개의 원판은 커다란 덩어리로 보자.

먼저 N-1개의 원판을 하노이의탑 규칙에 어긋나지 않게 A -> B 위치로 옮긴다.

그 뒤, N 번째 원판을 A -> C로 옮긴다.

다시 N-1개의 원판을 N-2번째 원판과 그 외의 원판들로 보자.

N-2 개의 원판들을 규칙에 어긋나지 않게 B -> A로 옮긴 후, N-1번째 원판을 B -> C로 옮긴다.

이를 반복하며 다시 N-2개의 원판들을 C로 옮긴다.

 

// n개의 원판을 from -> to로 이동
fun hanoi(int n, int from, int temp, int to) {
    if(n == 0) // 원판갯수가 0이면
    	return // 종료
    hanoi(n-1, from, to, temp)
    n번째 원판을 from -> to로 이동.
    hanoi(n-1, temp, from, to)
}

수도코드로 간단히 표기하면 위와 같다.

하나의 원판을 옮길때 재귀함수가 2번 호출되므로 시간복잡도는 O(2^N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/programmers/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98%20%ED%83%91.cpp