백준(BAEKJOON): 하노이 탑 이동 순서(11729번)

Source

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

예제 입력 1

3

예제 출력 1

7
1 3
1 2
3 2
1 3
2 1
2 3
1 3

해설

하노이 탑

눈으로는 이 문제를 푸는 방식을 알아냈다. 하지만 이를 다시 코드로 구현하는 것은 별개의 문제였다.

우선 이 문제 자체를 눈으로 풀어 보자. 3개의 돌(1, 2, 3번)이 있고 세 개의 막대 A, B, C가 있다. 돌은 숫자가 커질수록 크기가 커지며, A는 출발 막대, B는 경유 막대, C는 목적 막대이다. A에서 C로 탑을 이동하기 위한 돌의 이동은 크게 3단계로 구성된다. 가장 먼저 고려해야 하는 것은 A에서 가장 밑에 깔린 돌을 C로 이동해야 한다는 점이다. 이를 위해서 먼저 그 돌 위에 있는 모든 돌을 적절히 B로 옮겨야 한다. 그 다음으로 A의 가장 밑에 깔린 돌을 C로 이동한다. 그 후에서는 B에 옮겨 놓은 돌을 C로 이동해야 한다.

1. 2개(1, 2번째)의 돌을 A에서 B로 옮긴다.
2. 3번째 돌을A에서 C로 옮긴다.
3. 1.에서 빼놓았던 돌을 B에서 C로 옮긴다.

3 단계에서 공통적으로 보이는 "{출발지}에서 {목적지}로 옮긴다"는 반복되고 있으므로 이를 하나의 함수(예컨대 move(돌 번호, 출발지, 목적지) 함수)로 처리해야 할 것이다. 그 다음부터는 코드로 어떻게 구현해야 할지 막막했다. move() 함수가 실행되거나 반복되어야 할 조건을 어떤 식으로 구체화할 수 있을까? 루프를 쓴다면 종료 조건은 어떻게 만들어야 할까? 막대에 해당하는 배열을 만들어서 A 막대(배열)과 C 막대(배열)의 값이 동일해질 때까지 move() 함수를 호출하면 될까?

답답함과 시간 부족을 핑계로 구글링을 해보았다. 하이노탑의 해법을 코드로 구현하는 가장 단순한 방법은 재귀 함수를 쓰는 것이란다. 그럼 재귀 함수란 무엇일까? 분명 프로그래밍 언어를 재귀 함수 챕터를 본 기억은 있는데 기억나는 것은 아무것도 없다. 글자만 읽었을 뿐 재귀 함수를 제대로 이해하지 못했다는 것이 증명되는 순간이다.

재귀 함수란

재귀 함수(recursive function)란 함수 안에서 함수 자기자신을 호출하는 함수를 말한다. 이러한 방식을 재귀호출(recursive call)이라고 한다. "재귀호출은 일반적인 상황에서는 잘 사용하지 않지만 알고리즘을 구현할 때 매우 유용합니다. 보통 알고리즘에 따라서 반복문으로 구현한 코드보다 재귀호출로 구현한 코드가 좀 더 직관적이고 이해하기 쉬운 경우가 많습니다."라고 하는데 재귀 함수를 제대로 이해하지 못한 때문인지 내게 되려 이해하기 어려운 코드로만 보인다.

간단하게 보이면 아래의 hello() 함수가 재귀 함수이다.

def hello():
    print('Hello, World!')
    hello()

hello()

위 코드를 실행하면 "Hello, World!"가 무한히 찍히는 것을 확인할 수 있다. hello() 함수를 호출하면 print() 문이 실행되고 다시 자기자신인 hello()가 호출된다. 따라서 다시 print()문이 호출되고 다음으로 자기 자신인 hello()가 실행된다. 이렇게 무한히 자기자신을 호출하기 때문에 무한 루프가 된다. 프로그래밍 언어에 따라서는 최대 재귀 깊이(maximum recursion depth)가 한정되어 있는데 파이썬은 그 값이 1,000이다. 이를 초과할 경우 파이썬은 RecursionError를 반환한다.

재귀함수는 태생적으로 무한 루프가 되므로 종료 조건을 반드시 지정해 주어야 한다. 위의 코드를 재활용해 보자.

def hello(num):
    if num is 0:
        return
    print('{}: Hello, World!'.format(num))
    num -= 1
    hello(num)

hello(3)

위 코드를 실행하면 hello()의 int형 인자를 지정하고 그 수만큼 print()문을 실행하게 된다. 위의 경우라면 아래와 같이 출력된다.

3: Hello, World!
2: Hello, World!
1: Hello, World!

자, 이제 하노이 탑으로 돌아와 보자. 처음에 언급했듯이 하노이탑의 해법은 크게 아래의 3가지 동작으로 구성된다. 돌의 개수를 n으로 하여 다시 바꾸어 쓰면 아래와 같다.

1. n-1번째까지의 돌을 A에서 B로 옮긴다.
2. n번째 돌을 A에서 C로 옮긴다.
3. 1.에서 빼놓았던 n-1번째까지의 돌을 B에서 C로 옮긴다.

그런데 여기서 잡아내야 하는 부분은 1번의 동작도 "{출발지}에서 {목적지}로 옮긴다"라는 동작인 것이다. 1.번 동작은 n-1개의 하노이탑을 출발지에서 목적지로 옮기는 것이다. 즉 애초의 3층짜리 하노이탑을 옮기기 위해 2(n-1)층짜리 탑을 먼저 옮겨야 하는 것이다. 애초와 달리 목적지가 C에서 B로 바뀐 것이다. 이렇게 탑의 높이가 한 층씩 줄어들기는 하지만 결국 하나의 탑 전체를 옮긴다는 점에서는 처음의 동작을 계속 반복하게 된다. 즉 재귀 함수로 처리할 수 있음을 깨닫게 된다.

이제는 함수를 정의해보자.
우선 돌의 이동을 구현하는 함수가 필요하다. 돌의 번호와 이 돌의 출발지와 목적지를 인자로 받고 실행되면 그 이동 경로를 출력하는 함수이다.

def move(_n, _from, _to):
    print(_from, _to)

이제 탑의 돌을 옮기는 3단계를 재귀 함수로 구현하면 아래와 같다.

def hanoi(_n, _from, _to, _via):
    if _n is 1:
        move(_n, _from, _to)
    else:
        hanoi(_n - 1, _from, _via, _to)   
        move(_n, _from, _to)
        hanoi(_n - 1, _via, _to, _from)

이 재귀함수에 입/출력 코드를 추가하여 코드를 완성하면 아래와 같다.

소스코드: python3

def move(_n, _from, _to):
    tracked.append("{} {}".format(_from, _to))

def hanoi(_n, _from, _to, _via):
    if _n == 1:
        move(_n, _from, _to)
    else:
        hanoi(_n - 1, _from, _via, _to)
        move(_n, _from, _to)
        hanoi(_n - 1, _via, _to, _from)

tracked = list()
n = int(input())

hanoi(n, 1, 3, 2)

print(len(tracked))
for item in tracked:
    print(item)

소스코드: C

#include <stdio.h>
#include <math.h>

int move(int num, int from, int to, int via);

int main(int argc, char *argv[])
{
    int num;

    scanf("%d", &num);
    printf("%.0f\n", pow(2, num) - 1);
    move(num, 1, 3, 2);
    return 0;
}

int move(int num, int from, int to, int via)
{
    if (num == 1) {
        printf("%d %d\n", from, to);
    } else {
        move(num - 1, from, via, to);
        printf("%d %d\n", from, to);
        move(num - 1, via, to, from);
    }
    return 0;
}

c코드에서는 이동 횟수를 계산을 통해 구했다. 하노이탑의 이동 힛수는 (2 * 돌의 개수) - 1이다. 이동 관련 함수도 따로 만들지 않고 printf()로 바로 처리했다.