백준 11729 C#) 하노이 탑 이동 순서
재귀로 풀 수 있는 문제들 중에서도 상당히 유명한 편이다.
public static class PS
{
private static readonly StreamWriter sw;
static PS()
{
sw = new(new BufferedStream(Console.OpenStandardOutput()));
}
public static void Main()
{
int n = int.Parse(Console.ReadLine());
sw.WriteLine(Math.Pow(2, n) - 1);
Hanoi(n, 1, 2, 3);
sw.Close();
}
private static void Hanoi(int n, int from, int via, int to)
{
if (n == 0)
return;
Hanoi(n - 1, from, to, via);
sw.Write(from);
sw.Write(' ');
sw.WriteLine(to);
Hanoi(n - 1, via, from, to);
}
}
이 문제를 풀기 위한 아이디어는 두 가지 정도가 있겠다.
1. 가장 큰 원판은 무시할 수 있다.
다르게 말하자면 가장 큰 원판은 바닥이나 마찬가지라는 뜻이다. 나머지 원판들은 모두 그것보다 작기 때문에 자유롭게 이동할 수 있다.
2. 가장 큰 원판을 옮기려면 이를 제외한 나머지 원판들은 모두 중간 지점에 있어야 한다.
중간 지점은 출발 지점도, 도착 지점도 아닌 곳이다. 큰 원판을 도착 지점에 이동시키려면 당연히 도착 지점이 비어있어야 하고 (혹은 그것보다 더 큰 원판이 있거나) 출발 지점에는 큰 원판만 남아있어야 하므로 이를 제외한 나머지 원판들은 모두 중간 지점에 있어야 한다.
사실 이 문제가 유명하긴 하지만 쉬운 문제는 절대 아니라고 생각한다. (실제로 솔브닥 티어도 실버1 이다)
분할정복이나 DP 문제들을 여럿 풀다보면 훈련이 되는 부분이지만 초심자가 풀기에는 조금 무리가 있어보인다...
그러니 좀 더 자세하게 설명하도록 하겠다.
이해를 돕기 위해 플래시게임 화면을 캡쳐해왔다.
게임을 클리어하기 위해서는 모든 원판을 3번 타워에 옮겨야 하는데, 가장 먼저 아래의 그림이 나와야 한다.
우선은 가장 큰 원판을 3번 타워에 옮겨야 하므로 이를 제외한 나머지 원판들을 모두 중간 지점인 2번 타워로 이동시켰다.
어떻게 옮겼는지 궁금하다면, 이 모든 작업이 재귀로 이루어진다는 사실을 다시금 떠올려볼 필요가 있겠다...
아무튼 이제 가장 큰 원판을 도착 지점인 3번 타워로 이동시키겠다.
분명 이동시켰는데 원판이 그림에서 사라졌다. 그러나 이는 3번 타워에 가장 큰 원판을 옮긴 것과 다름이 없다.
왜일까? 위에서도 설명했지만 가장 큰 원판은 무시할 수 있기 때문이다. 그것보다 큰 원판은 없으므로 사실상 바닥이나 마찬가지인 것이다.
어쨌든 우리는 여전히 남은 원판들을 도착 지점인 3번 타워에 이동시켜야 하는데, 그림이 어딘가 익숙해보인다.
그렇다. 이는 원판이 하나 줄었을 뿐 사실상 새롭게 시작하는 것과 다를게 없다.
그리고 하노이탑은 이를 계속 반복할 뿐이었다...
이제 코드로 다시 돌아가보자.
private static void Hanoi(int n, int from, int via, int to)
우선 Hanoi는 4개의 인자를 갖는다. 차례대로 원판의 개수 n, 출발 지점 from, 중간 지점 via, 도착 지점 to이다.
가장 먼저 그려야 하는 그림은, 가장 큰 원판을 제외한 나머지 원판들을 모두 중간 지점으로 보내는 것이다.
Hanoi(n - 1, from, to, via);
자기 자신을 호출하되, 개수를 하나 줄이고 기존의 중간 지점인 via를 도착 지점으로 설정하였다.
물론 이동 과정에서 기존의 도착 지점인 to를 중간 지점으로 활용해야 한다. 그래야 이동이 가능하다.
이렇게 하면 나머지 n - 1개의 원판들을 모두 중간 지점으로 보낼 수 있고, 이제 가장 큰 원판을 도착 지점으로 보내야 한다.
sw.Write(from);
sw.Write(' ');
sw.WriteLine(to);
이게 가장 큰 원판을 보낸 것이다.
이걸로 어떻게 정답이 출력되는지 잘 이해가 안된다면 아직 재귀를 이해하지 못한 것이니 직접 그림을 그려보며 생각하는 시간을 가져보시라.
가장 큰 원판을 보냈으니 다음은 중간 지점에 위치한 n - 1개의 원판들을 도착 지점에 보내는 것이다.
Hanoi(n - 1, via, from, to);
기존의 중간 지점이 출발 지점이 되었다.
결국은 출발 지점만 달라졌을 뿐 n - 1개의 원판으로 새롭게 시작하는 것과 똑같아졌다.
아까 나머지 원판들을 중간 지점으로 옮겼을 때도 마찬가지였다. 도착 지점만 바뀌었을 뿐 n - 1개의 원판으로 새롭게 시작했던 것이다.
재귀란 이런 것이다. 매 순간이 새로운 시작, 이야기 속의 이야기...
퍼포먼스는 반복문이 더 좋지만 재귀 특유의 간결함은 분명 무시할 수 없는 부분이다.
참고로 횟수를 그냥 2의 거듭제곱에서 1을 뺀 수로 출력했는데, 이를 몰랐다면 가장 큰 원판을 보낼 때마다 횟수를 세어야 했을 것이다.
크게 상관은 없는데 그렇게 하려면 StringBuilder와 Insert 메소드를 이용해 맨 앞에 횟수를 삽입하거나 리스트에 답을 저장해두는 등의 과정이 필요할 듯하다.