[프로그래머스] 하노이의 탑 (Swift 풀이)

 

programmers.co.kr/learn/courses/30/lessons/12946

코딩테스트 연습 - 하노이의 탑

 

하노이탑은 어렸을 때 부터 무지 좋아하던 놀이이다!

보자마자 규칙은 떠올랐지만, 코드로 바꾸는게 조금은 헷갈렸던 문제...!

재귀함수 연습하기 딱 좋은 문제인 것 같다.

 

규칙 찾기

일단 규칙을 설명하기 위해 5개의 원판을 옮기는 상황을 가정해보자.

 

1. 5개의 원판을 1->3으로 옮겨야 한다.
   1. 1에 있는 원판 4개를 ->2로 옮겨야 한다.
   2. 1에 있는 원판 1개를 ->3으로 옮겨야 한다.
   3. 2에 있는 원판 4개를 ->3으로 옮겨야 한다.

이게 기본 규칙이다!!

 

그럼 위의 상황에서 나온 4개의 원판을 옮기는 상황은 다음과 같다.

1. 4개의 원판을 1->2로 옮겨야 한다.
   1. 1에 있는 원판 3개를 ->3으로 옮겨야 한다.
   2. 1에 있는 원판 1개를 ->2로 옮겨야 한다.
   3. 3에 있는 원판 2개를 ->2로 옮겨야 한다.
2. 4개의 원판을 2->3으로 옮겨야 한다.
   1. 2에 있는 원판 3개를 ->1로 옮겨야 한다.
   2. 2에 있는 원판 1개를 ->3으로 옮겨야 한다.
   3. 1에 있는 원판 3개를 ->3으로 옮겨야 한다.

규칙이 보이기 시작한다.

옮길 원판 갯수를 n, 시작 기둥을 start, 목적지 기둥을 end라고 하고,

start와 end가 아닌 나머지 기둥을 mid라고 해보자!

 

n개의 원판을 start -> end로 옮겨야 한다.

• n-1개의 원판을 start -> mid
• 1개의 원판을 start -> end
• n-1개의 원판을 mid -> end

 

 

재귀함수 구현

재귀함수로 구현할 수 있을 것 같다.

func move(n: Int, start: Int, end: Int) {
    let mid = getMid(start, end)
    
    move(n: n-1, start: start, end: mid)
    move(n: 1, start: start, end: end)
    move(n: n-1, start: mid, end: end)
}

 

mid를 구하는 함수는 다음과 같다!

func getMid(_ start: Int, _ end: Int) -> Int {
    if start == 1 {
        if end == 2 { return 3 }
        if end == 3 { return 2 }
    } else if start == 2 {
        if end == 1 { return 3 }
        if end == 3 { return 1 }
    } else if start == 3 {
        if end == 1 { return 2 }
        if end == 2 { return 1 }
    }
    return -1
}

 

move 함수는 동작은 하지만, 반환 조건과 반환 값이 없다.

이대로는 무한 재귀 호출에 빠지게 된다..!

반환 조건으로는 n == 1 이면 원판 1개를 start 에서 end로 옮겨주는 조건을 추가하자.

반환 값은 Int 형 2차원 배열로, 옮기는 과정을 담아서 반환한다.

func move(n: Int, start: Int, end: Int) -> [[Int]] {
    if n == 1 {
        return [[start, end]]
    }
    
    var answer = [[Int]]()
    let mid = getMid(start, end)
    
    answer.append( contentsOf: move(n: n-1, start: start, end: mid) )
    answer.append( move(n: 1, start: start, end: end) )
    answer.append( contentsOf: move(n: n-1, start: mid, end: end) )
    
    return answer
}

 

전체 코드

func solution(_ n:Int) -> [[Int]] {
    func move(n: Int, start: Int, end: Int) -> [[Int]] {
        if n == 1 {
            return [[start, end]]
        }
        
        var answer: [[Int]] = []
        let mid = getMid(start, end)
        
        answer.append(contentsOf: move(n: n-1, start: start, end: mid))
        answer.append([start, end])
        answer.append(contentsOf: move(n: n-1, start: mid, end: end))
        
        return answer                
    }
    
    return move(n: n, start: 1, end: 3)
}

func getMid(_ start: Int, _ end: Int) -> Int {
    switch start {
    case 1:
        switch end {
        case 2:  return 3
        case 3: return 2
        default: return -1
        }
    case 2:
        switch end {
        case 1: return 3
        case 3: return 1
        default: return -1
        }
    case 3:
        switch end {
        case 1: return 2
        case 2: return 1
        default: return -1
        }
    default:
        return -1
    }
}