2021-02-03

하노이의 탑(Tower of Hanoi)

피보나치와 더불어 재귀적으로 문제를 해결하면 좋은 대표 문제이다. 우선 맨 마지막 원판 위의 나머지 원판들을 임시 기둥으로 옮긴다.
written by

Introduction

하노이의 탑(Tower of Hanoi)은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다.

게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다.

  1. 한 번에 하나의 원판만 옮길 수 있다.
  2. 큰 원판이 작은 원판 위에 있어서는 안 된다.

Algorithm

피보나치와 더불어 재귀적으로 문제를 해결하면 좋은 대표 문제이다.

큰 흐름은 다음과 같다.

  • 맨 마지막 원판 위의 나머지 원판들을 임시 기둥으로 옮긴다.
  • 맨 마지막 원판을 목적한 기둥으로 옮긴다.
  • 임시 기둥에 있는 원판들을 목적한 기둥으로 옮겨준다.

이 과정에서 나머지 원판들에 대해서도 위의 과정을 똑같이 거친다. 이것을 재귀적으로 호출하면 마지막에는 원판이 한 개인 경우부터 위의 과정을 역으로 반복한다.

당연히 원판이 하나인 경우가 기저 사례(Base Case)가 되어야 한다.

Kotlin Scratch Code

// 원판을 옮기는 과정을 process 리스트에 기록하는 함수.
fun hanoi(process: MutableList<List<Int>>, first: Int, second: Int, third: Int, disc: Int) {
    when (disc) {
        // 원판이 한 개인 경우, 첫 번째 기둥에서 바로 마지막 기둥으로 옮겨준다.
        1 -> process.add(listOf(first, third))
        else -> {
            // 마지막 원판을 제외한 나머지 원판들을 두 번째 기둥으로 옮겨준다.
            hanoi(process, first, third, second, disc - 1)
            // 마지막 원판을 첫 번째 기둥에서 마지막 기둥으로 옮겨준다.
            process.add(listOf(first, third))
            // 나머지 원판들을 두 번째 기둥에서 마지막 기둥으로 옮겨준다.
            hanoi(process, second, first, third, disc - 1)
        }
    }
}

// 기록된 과정을 출력한다.
println(mutableListOf<List<Int>>().apply { hanoi(this, 1, 2, 3, 3) })

Result

[[1, 3], [1, 2], [3, 2], [1, 3], [2, 1], [2, 3], [1, 3]]
2021 © Cinntiq's Studio