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

문제 소개

정말 정말 유명한 문제 중 하나인 "하노이의 탑" 문제. 이 문제를 풀면서 정말 점화식, 재귀함수에 관련된 깊은 생각을 한 것 같다.

프로그래머스

아래와 같이 세 개의 기둥이 있고, 크기가 큰 원판부터 기둥에 꽂혀있다. 이제 이것을 크기가 작은 원판이 크기가 큰 원판보다 아래로 가지 않게 하면서, 한 번에 하나의 원판을 이동하며 세 번째 기둥으로 옮길 때 최소로 옮기는 방법을 return 하는 문제였다. 예를 들면, 2를 입력하게 된다면 2개의 원판이 1번에 있고, 이 원판을 세 번째 기둥으로 최소로 옮기는 방법은 [[1, 2], [1, 3], [2, 3]] 으로 총 세 번 옮기면 된다.

출처: 위키백과

 

문제 풀이

이 식은 정말 놀랍게도 점화식을 알게 된다면 아주 간단하게 해결이 가능하다.

import Foundation

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

 

하노이의 탑 점화식 구하기

아래와 같이 원판 4개가 있다고 생각해 보자. 이것을 최소한으로 3번 기둥에 옮긴다면?

 

아래와 같은 스탭을 걸쳐서 옮길 수 있다.

 

만약 4개의 원판을 옮긴다면...? 머리가 복잡해질 것이다. 하지만 간단한 방법이 있다. 우선 1번 기둥의 맨 아래 원판을 3번 기둥에 꽂으려면 어떻게 해야 할까?

 

아래처럼 만들 수밖에 없다. 작은 원판들을 다 치워야 제일 큰 원판을 옮길 수 있고, 원판이 하나도 없어야 3번 기둥에 가장 큰 원판을 놓을 수 있다.

그러면 아래와 같이 큰 원판을 3번 기둥에 꽂을 수 있다.

여기서 우리는 뭔가 느낄 수 있다. 그냥 4개 원판 옮기는 문제는 3개의 원판을 옮긴 후 마지막 원판을 옮기고 3개의 원판을 옮기는 문제와 같구나...!

 

// 하노이의 탑
4개원판옮기기 = 3개원판옮기기 + 1 + 3개원판옮기기
a(4) = a(3) + 1 + a(3)

 

그렇다면 점화식은 아래와 같다.

 

이 점화식을 통해서 하노이의 탑의 일반항은 아래와 같이 구할 수 있다.

 

하노이의 탑 점화식 코드로 바꾸기

위의 점화식은 재귀함수로 바꿀 수 있는데, 코드는 살짝 더 까다로운 조건이 들어간다. 단순히 최소 이동 횟수를 구한다면 위의 일반항을 통해 구할 수 있지만, 모든 과정을 출력하라는 프로그래머스 같은 문제가 나온다면...?

 

함수 선언

아래와 같이 시작, 목표, 중간을 입력받는 함수를 만들어준다.

/// 하노이의 탑
/// - Parameters:
///   - n: 원판 개수
///   - from: 시작 지점
///   - to: 목표 지점
///   - by: 중간 지점
/// - Returns: 과정
func hanoi(n: Int, from: Int, to: Int, by: Int) -> [[Int]] {
	
}

 

이 하노이탑 문제는 위의 함수에 따르면 아래와 같은 입력값을 넣으면 답이 나오게 만들 것이다.

// 하노이의 탑
hanoi(n: 4, from: 1, to: 3, by: 2)

 

우선 재귀함수이므로 탈출 조건을 만들어준다. 원판이 하나라면 시작과 목표를 [[시작, 목표]] 형식으로 return 한다.

func hanoi(n: Int, from: Int, to: Int, by: Int) -> [[Int]] {
    if n == 1 { return [[from, to]] }
    ...
}

 

아랫부분이 중요한데 우선 위에서 설명한 것처럼 3분 할로 나눠야 한다.

 

첫 번째는 중간 지점을 목표로 n-1개의 원판을 옮겨주는 것이다. 아래처럼 to에 by가 들어가고, by에 to가 들어간다. 왜냐하면 목표지점이 두 번째 기둥이 된 순간 세 번째 기둥은 중간지점이 되는 것이다. return 값에 hanoi(n: n-1, from: from, to: by, by: to)를 넣어준다.

func hanoi(n: Int, from: Int, to: Int, by: Int) -> [[Int]] {
    if n == 1 { return [[from, to]] }
    return hanoi(n: n-1, from: from, to: by, by: to) ... // 추가된 부분
}

 

두 번째는 가장 큰 원판을 시작 지점에서 목표 지점으로 옮겨준다. [[from, to]] 를 더해준다.

func hanoi(n: Int, from: Int, to: Int, by: Int) -> [[Int]] {
    if n == 1 { return [[from, to]] }
    return hanoi(n: n-1, from: from, to: by, by: to) + [[from, to]] ... // [[from, to]] 추가!
}

 

 

세 번째는 중간 지점에 있던 n-1개의 원판을 목표 지점으로 옮겨준다. 따라서 from에는 중간지점인 by가, to는 원래 목표지점인 to가 들어가게 된다. hanoi(n: n-1, from: by, to: to, by: from)를 더해준다.

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

 

이렇게 만들면 재귀함수가 뽈뽈뽈 일을 해주면서 놀랍게도 단 3줄의 함수로 모든 과정을 출력하게 만들 수 있다. 하노이의 탑을 보며 알고리즘과 점화식에 대한 중요성을 확인할 수 있었고, 코드를 어떻게 짜느냐에 따라 문제풀이가 얼마나 효율적으로 변할 수 있는지 깨달았다.

 

하노이의 탑 번외

만약 하노이의 탑에서 4개의 하노이의 탑이 있다면...?

 

아래와 같이 k 개를 하노이의 탑 규칙대로 이동시킨 뒤 (그림상에선 2개지만 k라고 생각해 보자...)

n-k개를 옮기고, k개를 마저 옮겨주면 된다. (하노이탑 두 번 나눠서 하기! 정도로 생각하면 될 것 같다)

 

여기서 이동 횟수가 최소가 되는 k값은 n=4일 때 1, 2이고, n=5일 때 2, 3이라고 한다. 그래서 일반항을 검색해 봤는데... 그만 알아보기로 했다. 😂 (추후 시간이 많을 때...)

출처: http://mathought.com