[백준] 11729번 : 하노이 탑 이동 순서 - Swift

문제

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

 

코드

var num = Int(readLine()!)
var result = 1
for _ in 0..<num!
{
    result *= 2
}
print(result - 1)

hanoi(n: num!,from: 1,by: 2,to: 3)

func move(from:Int, to:Int)
{
    print("\(from) \(to)")
}

func hanoi(n:Int, from:Int, by:Int, to:Int)
{
    if(n==1)
    {
        move(from: from, to: to)
    }
    else
    {
        hanoi(n: n-1,from:from, by:to, to:by)
        move(from: from, to: to)
        hanoi(n: n-1, from: by, by: from, to: to)
    }
}

 

https://www.youtube.com/watch?v=FYCGV6F1NuY 

 

 

분할정복 문제를 풀어보기 위하여 11729번을 선택했다. 이 알고리즘에서는 어디서 어디를 거쳐 어디로 가는지가 중요하다. n개의 탑이 있을때, 1~n-1번째 탑들은 from에서 to를 거쳐 by로 놓아야한다. n번째 탑은 from에서 by를 거쳐 to에 놓는다. 다음으로 1~n-1번째 탑들은 by에서 from을 거쳐 to로 옮기면 모든 탑들을 옮길 수 있다. 이 과정을 재귀함수로 표현하면 직관적으로 해결할 수 있다. 하지만 재귀함수는 이게 왜 되지!!싶을 때가 많은 것 같다.