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

Problem

 

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

---

Solution

 

이번 문제의 핵심은 재귀를 이용하는 것 입니다.

 

아래와 같이 n개의 원판이 1번 기둥에 모두 있습니다.

 

1. 1번 기둥에 있는 원판 중 가장 무거운 원판을 제외한 원판(n-1개)을 모두 2번 기둥으로 옮깁니다. 

 

 

 

2. 가장 무거운 원판을 3번 기둥으로 옮깁니다.

 

 

 

3. 2번에 있는 n-1개의 원판을 모두 3번으로 옮깁니다.

 

 

 

 

하노이의 탑을 푸는 과정을 간단하게 설명드리면 위와 같이 진행됩니다.

 

하지만 여기서 의문이 들죠?

 

 

"전체적인 과정은 알겠어... 근데 n-1개의 원판들을 어떻게 한번에 옮겨?🤔"

 

 

여기서 재귀 호출이 필요합니다.

 

바로 큰 문제를 작은 것으로 만들어서 하나 하나 풀어가는 것이죠.

 

자, 먼저 4개의 원판이 있다고 가정할게요.

 

여기서 2번 기둥에 n-1개 즉, 3개의 원판을 옮겨야 하죠?

 

하지만 한 번에 3개의 원판을 옮길 수는 없습니다.

 

 

그럼 더 작게 먼저 위의 2개의 원판을 옮기도록 해보겠습니다.

 

하지만 2개의 원판도 옮길수가 없죠?

 

 

 

더 작게 1개의 원판만 옮기도록 해보겠습니다.

 

1개의 원판은 옮길 수 있으므로 2번 기둥으로 옮깁니다.

 

 

 

자 이렇게 가장 작은 단위의 문제를 해결했습니다.

 

그러면 바로 전 단계의 문제인 2개의 원판 옮기기에 도전해보죠.

 

먼저 두 번째로 가벼운 원판을 3번 기둥으로 옮깁니다.

 

 

2번에 있던 가장 가벼운 원판을 1번 기둥으로 옮긴 뒤 3번 기둥에 있는 원판을 2번 기둥으로 옮깁니다.

 

 

마지막으로 1번 기둥의 원판을 2번 기둥으로 옮깁니다.

 

 

---

 

이런식으로 작은 문제들을 하나씩 해결해 나가면 n-1개의 원판을 2번 기둥으로 옮길 수 있겠죠?

 

바로 이것이 작은 문제를 해결해 나가면서 가장 큰 문제를 해결하는 것이 바로 재귀 알고리즘입니다.

 

코드 설명

 

이제 코드로 알아보겠습니다.

 

가장 먼저 옮기는 과정을 담을 answer를 만들어줍니다.

 

var answer: [[Int]] = []

 

먼저 원판을 옮길 수 있는 조건을 만들어줍니다.

 

원판을 옮길 수 있는 조건은 원판이 1개 남았을 때 입니다.

 

고로 n이 1이라면 answer에 from에서 to로 옮긴 과정을 넣어줍니다.

 

func move(n: Int, from: Int, to: Int, via: Int){
    if n == 1 {
        answer.append([from,to])
    }

 

1. 만약 n이 1이 아니라면 1번에서 2번 기둥으로 옮기는 작업을 재귀 호출해줍니다.

 

else {
        move(n: n-1,from: from, to: via, via: to)

 

2. 다 옮긴 다음엔 1번 기둥에 있는 가장 무거운 원판을 3번 기둥으로 옮기는 작업을 넣어줍니다.

 

answer.append([from,to])

 

3. 마지막으로 2번 기둥에 있는 모든 기둥을 옮기는 작업을 재귀 호출해줍니다.

 

move(n: n-1, from: via, to: to, via: from)

---

Source Code