문제 풀이 아이디어

하노이의 탑은 전형적인 재귀함수 문제입니다.

먼저 n을 1부터 늘려가면서 규칙을 찾아보도록 하겠습니다.

n이 1일 때는 바로 1에서 3으로 1번 옮기면 됩니다. ([[1, 3]])

n이 2일 때는 작은 블록을 잠시 2로 옮겨두었다가, 큰 블록을 3으로 옮기고 나서 다시 작은 블록을 2에서 3으로 옮기면 됩니다. ([ [1,2], [1,3], [2,3] ])

n이 3일 때는 작은 블록과 중간 블록 (n = 2일 때와 같은 블록 2개)를 2로 잠시 옮겨두었다가, 가장 큰 블록을 3으로 옮기고 나서 작은 블록과 중간 블록을 2에서 3으로 옮기면 됩니다.

n이 4일 때는 가장 큰 블록을 제외한 나머지 3개의 블록 (n = 3 일 때와 같은 블록 3개)를 2로 잠시 옮겨두었다가, 가장 큰 블록을 3으로 옮기고 나서 나머지 3개의 블록을 3으로 옮기면 됩니다.

위 규칙을 일반화해서 정리하면 아래와 같습니다.

n개의 블록, from이 출발지, to가 목적지, mid가 중간에 잠시 옮겨두는 곳일 때

(n - 1개의 블록을 from에서 mid로) + (1개의 블록을 from에서 to로) + (n - 1개의 블록을 mid에서 to로)

코드

위에서 찾은 공식을 재귀함수를 활용해서 코드로 구현하면 아래와 같습니다.

func hanoi(n: Int, from: Int, to: Int) -> [[Int]] {
    if n == 1 { return [[from, to]] }
    let mid = 6 - from - to
    return hanoi(n: n - 1, from: from, to: mid) + [[from, to]] + hanoi(n: n - 1, from: mid, to: to)
}

func solution(_ n:Int) -> [[Int]] {
    return hanoi(n: n, from: 1, to: 3)
}