[Swift] 재귀 BOJ11729 하노이의 탑

나름 이 문제의 핵심인 것 같아 가져온 문장이다.
“너무 깊숙히 들어가지 맙시다. 깊숙히 들어가는 건 컴퓨터가 알아서 해줄 거예요.”

규칙을 찾아보자
사진 속 5개 를 기준으로 보자면

단계 1

(원판 개수:5개, 출발 장대: 1번, 목적지 장대:3)

1. 1번 장대에서 원판 4개를 2번 장대로 옮긴다
2. 1번 장대에서 나머지 원판 1개를 3번 장대로 옮긴다
3. 2번 장대에서 원판 4개 모두를 3번 장대로 옮긴다

단계 2(단계 1의 3번)

(원판 개수:4개, 출발 장대: 2번, 목적지 장대: 3번)

1. 2번 장대에서 원판 3개를 1번 장대로 옮긴다.
2. 2번 장대에서 나머지 원판 1개를 3번 장대로 옮긴다.
3. 1번 장대에서 원판 3개 모두를 3번 장대로 옮긴다.

단계 3(단계 2의 3번)

.
.
.

*** 생략

마지막-1 단계

1. 2번 장대에서 원판 1개를 1번 장대로 옮긴다.
2. 2번 장대에서 나머지 원판 1개를 3번 장대로 옮긴다.
3. 1번 장대에서 원판 1개를 3번 장대로 옮긴다.

마지막 단계

원판 한개를 3번 장대로 옮기는게 목표이므로 그냥 3번 장대로 옮긴다.

---

이를 바탕으로 구현하면

import Foundation

func move(_ start:Int, _ dest:Int) { answer +=  "\(start) \(dest) \n"; count += 1 }

func Hanoi(_ n: Int, _ start: Int, _ by:Int, _ dest: Int) {
 if(n == 1) { move(start,dest) }
 else {
   Hanoi(n-1,start,dest,by) // dest-start = 거쳐가는 원판 (목적지,출발지 원판을 제외한 나머지 원판)
   move(start,dest)
   Hanoi(n-1,by,start,dest)
 }
  
}

let n = Int(String(readLine()!))!
var answer = ""
var count = 0
Hanoi(n,1,2,3)
print(count, answer, separator: "\n")