'하노이의 탑' 이해하기 (feat. 재귀 함수)

1. 들어가며
2. 하노이의 탑
   1. 문제 소개
   2. 문제 정의
3. 아이디어 얻기
   1. 아이디어
   2. 재귀
   3. 출발점, 도착점, 경유점
   4. 문제 분해
4. 실제 코드
5. 번외 : 원반의 개수에 따른 총 이동횟수 구하기
6. 마무리
7. 자료 출처

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

1.  들어가며

백준 11729번 문제에 관한 내용으로, 이번 내용은 '하노이의 탑' 알고리즘이다. '하노이 의 탑'은 재귀를 연습하기에 매우 좋은 연습문제다.
코드 자체보다 코드에 이르는 과정이 더 중요하다. 문제를 정의하고, 문제를 풀기 위한 핵심 아이디어를 살펴보자. 
그리고나서 이 통찰력을 사용해서 코드로 유도하자. 그리고 코드를 살펴본 후 탑의 개수에 따른 총 이동횟수를 구해보자.
이때는 단순히 재귀식이 아닌, 일반항을 유도해 보도록 하자.

---

2. 하노이의 탑

먼저 문제를 이해해 보자. 이 문제가 요구하는 바를 파악하고, 어떤 것을 출력할 것인지 정해보자.
어떤 것을 출력할 것인지에 따라 코드 형태가 달라지기 때문에, 이점을 확실히 생각하고 가자.

2.1 문제 소개

'하노이의 탑'(Tower of Hanoi)은 프랑스의 수학자 에두아르 뤼카가 1883년 소개한 문제이다.
아래 그림으로 표현할 수 있다.

하노이의 탑

3개의 막대(기둥)가 있고, 첫 번째 막대에 5개의 원반이 쌓여있다. 각 원반의 크기는 모두 다르고, 아래에서부터 위로 갈수록 점점 작아진다.

우리의 목표는 막대 'A'에 쌓여있는 원반들을 그 순서를 지키면서 그대로 'C'로 옮기는 것이다. ('B'로 옮겨도 상관은 없다)

하노이의 탑

이때 원반을 옮기는 몇 가지 조건이 따른다.

• 한 번에 움직일 수 있는 원반은 기둥 위에 놓인 원반 하나뿐이다.
• 어떤 원반 위에 그보다 더 큰 원반을 쌓을 수 없다.

이 조건 하에서 '최소의 이동횟수로 옮기는 가짓수'를 구하거나, '최소의 이동횟수로 옮길 때 각 원반을 옮기는 순서'등을 구하는 것이 하노이의 탑 문제가 된다.

2.2 문제 정의

이제 문제 자체는 이해했으니, 이를 체계적으로 정의해보자. "체계적"이라함은, 문제의 입력과 출력을 보다 함수에 가깝게 정의하자는 것이다. 우리는 "원반의 이동횟수를 최소화하고자 할 때, 각 원반을 옮기는 모든 순서를 출력하는 것"으로 한다. 이때 각 이동의 출력은 '3번 원반을 A에서 C와 같이로 정하며, 입력은 원반의 개수로 받는다.

이를 구현하는 함수 hanoi를 대략적으로 정의하면 다음과 같다.

hanoi(N): 원반의 개수 N을 입력 받아 모든 원반을 "C" 막대에 옮기는 각 움직임을 출력한다.

---

3. 아이디어 얻기

위에서 문제를 매우 러프하게(대략적으로) 정의했다. 
각 원반을 어디에서 어디로 옮기는지를 모두 출력해야 하며 그를 위해서는 실제 움직임을 추적하고 문제해결을 위한 핵심 아이디어를 포착해야 한다.

어떻게 아이디어를 포착할까? 어떤 알고리즘 문제라도, 감각적으로 아이디어가 안 떠오를 때 가장 먼저 시도해 볼 수 있는 것은, 실제로 하나씩 해보는 것이다. 이 문제에서는 실제로 원반을 하나씩 옮겨보는 것이다.
중요한 것은,  문제를 작게 축소해서 시도해서 해결해보고, 그것을 확대하는 것이다. 

한번 해보자. 우선 원반(n) 3개로 시작해보자. 그리고 나서 얻은 통찰을 확인해 보자.

원반의 개수가 3개일 때, 각 움직임을 표현하는 그림이다. 이동횟수를 최소로 할 때 총 7번을 이동해야 하며 정해진 규칙을 지키면서 최종적으로 'C'막대에 모든 원반이 위치하게 된다. 각 움직임을 눈으로 쫓아 생각해보기 바란다. 원반이 2개, 4개일 때를 직접 그려보는 것도 좋다.

앞서 hanoi(N) 함수는 각 움직임을 한 문장씩 출력한다고 했다. 우리가 원하는 함수 hanoi(3)의 실행결과는 다음과 같을 것이다.

1번 원반을 A에서 C로 이동
2번 원반을 A에서 B로 이동
1번 원반을 C에서 B로 이동
3번 원반을 A에서 C로 이동
1번 원반을 B에서 A로 이동
2번 원반을 B에서 C로 이동
1번 원반을 A에서 C로 이동

이제, 우리가 할 것은 작은 입력을 통해 문제를 직접 풀어본 뒤, 이를 통해 문제 해결을 위한 통찰, 즉 핵심 아이디어를 얻는 것이다.
그 아이디어를 바탕으로 문제를 프로그래밍 가능하게 보다 구체적으로 재정의 할 것이다.

3.1 문제 풀이 접근(아이디어)

원판이 n개일떄를 생각해보자.

출처: 밤샘공부

우리는 n개의 원판을 세번째 기둥에 옮겨야 한다.
편의상 아래와 같이, 1번막대, 2번막대, 3번막대로 칭하겠다.

출처: 밤샘공부

이제 n개의 원판을 1번막대에서 3번막대로 옮기는 것을 각 단계로 나누어 생각해 보자.
총 3단계로 나눌 수 있다. (변화가 있는 원판은 노란색)

1단계에서는 n-1 개의 원판을 1번 막대에서 2번막대로 옮긴다.

2단계에서는 남은 1개의 원판을 1번 막대에서 3번 막대로 옮긴다.

3단계에서는 다시 n-1개의 원판을 2번 막대에서 3번 막대로 옮긴다.

이렇게 총 3단계로 구성되있는 루프가 이 문제를 푸는 핵심 아이디어이다.

3.2 재귀

재귀는 이 문제의 성패를 가르는 통찰이다. 재귀(recursion)란 같은 형태의 보다 작은 입력을 지닌 자기 자신을 호출하는 것이고, 이렇게 재귀적인 호출을 사용하는 함수를 재귀함수라고 한다.

이 문제에서 재귀의 여지가 있을까? 우선, 우리가 앞서 정의한 함수의 정의를 다시 보자.

• hanoi(N) : N개의원반을 어쩌고 저쩌고 해서 다른 곳으로 옮겨라.

이때 위의 7번 움직임은 모두 hanoi(N)의 과정이다. 그러면 hanoi(N-1)은 뭘까? 정의에 따라 다음과 같을 것이다.

• hanoi(N) : (N-1)개 원반을 어쩌고 저쩌고 해서 다른 곳으로 옮겨라.

충분히 가능한 해석이다. 내가 원하는 것은 재귀를 사용할 수 있도록,
hanoi(N)에서 hanoi(N-1)이 발견되냐는 것이다. 이를 현재 문제에 적용하면 hanoi(3)이니, hanoi(2)가 발견되는지가 될 것이다.

이 조건이 충족될 때 재귀를 전략적으로 사용할 수 있다.

단서는 2번 찾을 수 있다.
우선, 맨 처음을 보자. 규칙에 따라 3번째 원반을 "A에서 C"로 옮기려면 위의 두 원반은 'B'에 이미 꽂혀 있어야 한다. 즉, 이때 hanoi(2)가 필요하다고 보여진다.
두번째 단서는, 위 그림의 4번째 움직임에서 찾을 수 있다.  2개의 원반을 "B"에 꽂은 후 3번째 원반을 "C"로 옮겼다. 이제 2개의 원반을을 "B"에서 "C"로 옮겨야 한다. 여기서도  hanoi(2)가 보인다.

여기서 알 수 있는 것은 hanoi(N)은 두 번의 hanoi(N-1) 재귀 과정을 수반한다는 것이다.

3.3 출발점, 도착점, 경유점

재귀의 가능성을 찾은 것은 큰 성과다. hanoi(N)함수를 어떻게든 hanoi(N-1)를 활용한 형태로 표현 가능할 것 이라는 단서를 찾았다. 근데 추가적인 정보가 필요하다.

앞서 N개의 원반을 옮기는 작업에는 두 번의 재귀 과정이 있다고 했다. 이때 각 재귀 과정이 의도하는 바가 조금씩 다르다. 위의 그림을 참고하면 다음과 같이 구분할 수 있다.

• 첫 번째 재귀 : N-1 개의 원반을 "A"에서 "B"로 옮긴다.
• 두 번쨰 재귀 : N-1 개의 원반을 "B"에서  "C"로 옮긴다.

두 재귀는 옮기는 원반의 개수는 같지만 원반을 움직이는 출발지와 목적지가 다르다. 그리고 이 정보는 현재 러프하게 정의한 hanoi(함수에서 추적하지 않고 있는 정보이기도 하다. 우리의 문제 정의에서 출력은 각 움직임의 출발지와 목적지도 같이 기술해야 하기 때문에 함수에서 이 두 정보를 같이 추적해 주어야 한다. 따라서 원 함수의 입력이 원반의 개수만 받았다면 이제는 최소 출발지, 도착지의 변수까지 추가로 받아야 한다.

여기에 더해 "경유점" 이라는 개념도 사용하자. 만약 "A"에서 "C"로 3개의 원반을 이동할 때 "B"막대도 결국 사용해야 한다. 이렇게 세 개의 입력을 같이 입력해줘야 원반을 하나씩 이동할 때 경유점을 지날 때도 문제없이 출력할 수 있다.

3.4 문제 분해

이제 문제 해결과 관련된 핵심 재귀식을 만들어 보자. 앞선 그림에서 순차적으로 얻을 수 있다.
먼저, 보다 구체화된 문제를 다시 한 번 정의해보자.

hanoi(N, start, end, sub): start에서 sub를 거쳐 end로 총N개의 원반을 운반할 때 각 이동 과정을 출력하라

앞선 문제보다 훨씬 구체화 됐다. 그러면 위의 3개의원반을 옮기는 과정은 다음 함수로 표현할 수 있다.

• hanoi(3, "A", "C", "B") 

그리고 hanoi함수는 두 번의 재귀와 한 번의 가장  큰 원반을 옮기는 과정이 필요하다고 했다.
즉, 전체 과정을 세 과정의 연속으로 분해가능하다. (위에서 언급했음)

1. hanoi(2, "A", "B", "C"): "A"에서 "C"를 거쳐 "B"에 1번 2번 원반을 옮긴다.
2. 이후, start에 있는 3번원반을 "C"지점으로 옮긴다.
3.hanoi(2, "B", "C", "A") : "B"에 있는 두개의 원반을 "A"를 거쳐 "C"로 옮긴다.

원반의 개수(N)가 몇 개가 되든, 결국 이 과정을 거친다. 한 번의 재귀, 가장 큰 원반 옮기기 이후 다시 한번의 재귀, 물론 종료구문이 필요하다. N이 1일 때는 자신의 위 원반이 없기 때문에 재귀가 필요없고, 바로 원반을 옮기고 종료한다.

(hanoi(N, start, end, sub) == hanoi(N, start, to, via)임을 감안하고 아래 수식을 볼 것.)

각 재귀함수에서 인자의 순서를 햇갈리시 쉽다. 햇갈리지 말자.

1. 첫 번쨰 재귀에서는 맨 밑의 N번째 원반을 목적지로 옮기기 위해 위에 있는 N-1개의 원반을 경유지로 옮긴다.
2. 그 다음 N번째 원반을 목적지로 옮긴다.
3. 경유지에 있는 N-1개의 원반을 목적지로 옮긴다.

hanoi 함수의 파라미터중에 start, end, sub는 각각, 촐발기둥, 목표기둥, 보조기둥을 의미한다.
hanoi라는 재귀 함수를 이용하여 원판을 앞서 설명한 3단계의 방식으로 옮긴다.
해당 3단계의 방식을 1번 이상 거치면서 3번기둥으로 완전히 동일한 순서로 원판이 놓아지도록 옮겨지게 되는데,
이때 1단계와 3단계에서는 , 출발기둥, 목표기둥, 보조기둥이 바뀌게 된다.

처음에는 문제에 주어진 출발지점과 목표지점을 고려하여 1번기둥이 start, 2번기둥이 sub, 3번기둥이 end다.
즉, 함수는 처음에 hanoi(원판의 개수(n), 출발 기둥(start), 목표 기둥(end), 보조기둥(sub)) 의 형태로 파라미터를 받게 된다.

1단계에서는 start에 있는 n-1개의 원판을 모두 sub기둥으로 옮겨야 한다. 즉 1단계의 묙표기둥은 2번기둥이다.
그리고 보조기둥은 end기둥이 된다. 따라서 재귀를 이용할 때, 함수 인자로는 (n-1, start, sub, end)를 받게 된다.

이때 재귀 종료문으로 n이 1일때 종료 되도록 설정하고 return을 한다. 왜냐하면 n이 1개라면 재귀를 이용하지 않아도 되기 때문이다.

1단계를 거치고 나면 2번기둥(sub)에 n-1개의 원판이 모두 옮겨진다.

2단계에서는 비어있는 3번 기둥(end)기둥에 1번에 남은 기둥(가장 큰 원판)을 옮긴다.

3단계에서는 2번기둥으로 옮긴 n-1개의 원판을 3번기둥으로 옮기게되는데,
이때는 2번기둥이 출발기둥이 되고, 1번기둥이 보조기둥, 3번기둥에 목표기둥이 된다.
따라서 재귀를 호출 할 때 삽입되는 인자는 (n-1, sub, end, start)를 받게 된다. 

이것이 핵심이다. 이러면 정말 풀릴까? 라는 생각이 들 수도 있다.
코드를 짜고 실행시켜 보자.

문제 풀이 코드

재귀함수는 많은 경우 재귀식을 표현 할 수 있으면 그대로 풀린다. 위에서 정의한 함수 그대로 코드를 작성해 보자.

MSG_FORMAT = "{}번 원반을 {}에서 {}로 이동"

def move(N, start, end): # 원반을 실제로 옮기는 함수(출력)
	print(MSG_FORMAT.format(N, start, end))

먼저, 실제로 원반을 옮기는 move 함수를 정의한다. 메시지 형식은 위에서 정의한 그대로 사용한다.
이때 기억해야 할 것은, 실제 데이터와 데이터를 표현하는 형식은 별개이므로, 이 둘을 분리하면 좋다. MSG_FORMAT 은 형식에 불과하고, 실제 데이터는 N, start, end다. 이렇게 역할에 맞게 분리하는 습관을 들이자.

def hanoi(N, start, end, sub):
    if N == 1:
        move(1, start, end)
        return
    else:
        hanoi(N-1, start, sub, end)
        move(N, start, end)
        hanoi(N-1, sub, end, start)
hanoi(3, "A", "C", "B")

정말로 위에서 정의한 재귀식 그대로 함수를 만들었다. 기억하자. 설계가 코딩에 앞선다. 설계 없는 코딩은, 전기와 노동력, 시간을 잡아먹는 어리석은 짓이다.

[출력 결과]

1번 원반을 A에서 C로 이동
2번 원반을 A에서 B로 이동
1번 원반을 C에서 B로 이동
3번 원반을 A에서 C로 이동
1번 원반을 B에서 A로 이동
2번 원반을 B에서 C로 이동
1번 원반을 A에서 C로 이동

이렇게 원반을 옮기는 각 과정을 추적하는 형태의 하노이 탑 알고리즘 문제는 해결했다.

---

5. 번외 : 원반의 개수에 따른 총 이동횟수 구하기

앞선 '문제 정의' 절에서 우리는 원반을 움직이는 각 이동의 과정을 출력하도록 하노이의 탑 문제를 정의했다.
하지만, 이번에는 조금 다른, 상대적으로 수학적인 하노이의 탑 문제를 풀어볼 것이다.
원반의 개수가 N일 때, 원반을 모두 옮기는 데 드는 이동 횟수는 몇 번일까?

확실히 앞선 문제와는 결을 달리 한다. 앞서 작성한 함수는 원반의 개수가 3일 때, 7번의 print문이 실행되는데 이번 문제에서는 이렇게 7을 구하면 된다. 즉, 이번 문제는 원반의 개수 N에 따른 하노이의 탑 이동횟수에 대한 일반식을 구할 수 있을까? 이고, 확실히 앞선 문제에 비해 수학적이다.

천천히 접근해서 먼저 함수를 정의하고 시작하자. 앞선 함수는 원반의 개수(N뿐 아니라 출발지와 목적지에 대한 정보도 필요했다. 어디에서 어디로 옮기는지를 모두 출력해야 했기에 당연하다. 하지만 이 문제에서는 구체적인 출발지와 목적지에 대한 정보는 필요없다. 단순히 총 이동횟수만 구하면 되기 떄문이고 따라서 이번 함수에서는 이 정보들은 무시한다. 결국 함수를 정의하면 다음과 같을 것이다.

hanoi(N): N개의 원반을 옮기는 하노이의 탑 문제의 총 이동 횟수를 구하라

이때 각 함수는 마찬가지로 재귀식으로 짤 수 있다.

앞선 함수와 핵심 재귀 논리는 동일하다.
원반의 개수가 1개일 때는 바로 옮기면 되고, 그렇지 않다면, 위의 원반을 옮기고 자신을 옮긴 뒤 다시 남은 원반을 목적지로 옮긴다.

이 재귀식에서 일반항을 어떻게 도출할 수 있을까? 

이렇게 N개의 원반을 옮기는 하노이의 탑 문제의 이동횟수의 일반항을 구했다.
결국 2의 지수식이 나오는데, 각 함수가 두번의 재귀식을 실행시킨다는 것을 알면 대충 유추할 수도 있었을 것이다.
문제에 대한 감각이 중요..

---

6. 마무리

하노이의 탑 문제를 풀어보았다.
이 문제는 병합정렬과 마찬가지로 "재귀" 를 연습하는 데 정말 좋은 문제이다.
이 문제를 해결하면서,

1. 재귀
2. 출발점, 도착점, 경유
3. 문제 분해

세 개의 인사이트를 발견했고, 이를 통해 각 움직임을 포착하는 함수를 작성 할 수 있었다.
번외로, 각 움직임을 포착하는 것이 아닌, 총 이동 횟수를 구하는 일반항까지 구할 수 있었다.

---

7. 자료 출처

• 하노이의 탑: wikepedia
• Parkito

 

하노이의 탑