재귀를 이용한 알고리즘
아래 문제는 프로그래머스에서 제공하는 하노이의 탑의 문제입니다🧑🏻💻
문제 제시
하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.
- 한 번에 하나의 원판만 옮길 수 있습니다.
- 큰 원판이 작은 원판 위에 있어서는 안됩니다.
하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.
1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.
제한사항
- n은 15이하의 자연수 입니다.
입출력 예
| 2 | [ [1,2], [1,3], [2,3] ] |
입출력 예시
다음과 같이 옮길 수 있습니다.
문제 해결
import Foundation
var result: [[Int]] = []
func solution(_ n:Int) -> [[Int]] {
hanoi(n: n, from: 1, to: 3, by: 2)
return result
}
private func hanoi(n: Int, from: Int, to: Int, by: Int){
let tmp: [Int] = [from, to]
if n == 1 {
result.append(tmp)
print("최상단 원판을 \(from)에서 \(to)로 이동")
} else {
hanoi(n: n-1, from: from, to: by, by: to)
print("원판\(n) 을 \(from)에서 \(to)로 이동")
result.append(tmp)
hanoi(n: n-1, from: by, to: to, by: from)
}
}사용된 개념
- 재귀함수
문제 뒷담화
이번 문제는 재귀함수를 적극적으로 활용하여 문제를 푸는 대표적인 알고리즘이였다.
재귀함수는 그 안에서 함수를 또 다시 호출하는것을 말한다.
재귀함수가 성립되려면 조건을 꼭 부여해주어야한다. 즉 무한루프를 돌지 않게 탈출되는 조건을 주어야한다.
하노이의 탑 문제를 예를들면 원판의 갯수를 n이라 하였는데 나는 여기서 n을 원판의 번호로 생각했다.
즉, 원판이 밑의 깔린게 큰수 최상단 원판이 1이라고 생각하여 최상단 원판을 접근하면 재귀가 끝난다.
그렇게 되면 n의 갯수에 따라 재귀를 돌것이다.
아래와 같이 출력문을 찍어보면 흐름 순서를 쉽게 알 수 있다.
재귀함수를 전부 계속 돌며 호출시키고 난 뒤 제일 뒤늦게 호출된 함수의 출력부터 시켜 스택과 같이 차례대로 나타난다.
재귀를 도는 조건을 시작점, 끝점, 중간점을 두어 이 세개의 지점을 파라미터로 변경해주면서 돌게된다.
재귀를 돌며 이동된 위치 정보값을 2차원 배열에 추가해주고 해당 함수 호출이 끝난 후 메인 함수에서 결과값을 반환해주면 된다.