[BAEKJOON] 백준 11729: 하노이 탑 이동 순서(C#)

문제 링크

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

 

 

문제

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

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

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

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

입력

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

출력

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

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

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

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

 

 

통과한 답안

using System.Text;

namespace _11729
{
    internal class Program
    {
        static StringBuilder moves = new StringBuilder();
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            int totalMoves = CalculateMoves(N);
            Console.WriteLine(totalMoves);

            Move(N, 1, 3, 2);

            Console.WriteLine(moves.ToString());
        }

        static int CalculateMoves(int n)
        {
            if (n == 1) 
                return 1;
            else
                return 2 * CalculateMoves(n - 1) + 1;
        }

        static void Move(int n, int from, int to, int via)
        {
            if (n == 1)
            {
                moves.AppendLine($"{from} {to}");
            }
            else
            {
                Move(n - 1, from, via, to);

                moves.AppendLine($"{from} {to}");

                Move(n - 1, via, to, from);
            }
        }
    }
}

 

재귀 관련 알고리즘 문제에서 많이 나오는 문제인 하노이의 탑 문제이다.

하노이의 탑을 간략히 설명하면 N개의 서로 다른 크기의 원반이 탑으로 쌓여있을 때,

큰 크기의 원반은 작은 크기의 원반 위에 쌓을 수 없는 규칙을 갖고 있다.

이 때 한 번에 하나의 원반씩 이동시키는 경우 몇 번만에 탑을 다른 곳으로 이동시키는지를 묻는 문제이다.

 

이 문제에서 묻는 것은 이동 횟수에 더해서 원반의 이동 기록을 같이 묻고 있다.

만약 이동 횟수만 묻는다면 아래의 코드로도 문제를 풀이할 수 있는데

 

namespace _11729
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            int totalMoves = CalculateMoves(N);
            Console.WriteLine(totalMoves);
        }

        static int CalculateMoves(int n)
        {
            if (n == 1) 
                return 1;
            else
                return 2 * CalculateMoves(n - 1) + 1;
        }
    }
}

 

CalculateMoves를 선언하고 하노이 탑의 이동 횟수를 계산하는데

탑의 이동 횟수는 재귀를 통해 구할 수 있으며

원반이 하나인 경우 1번만에 이동시킬 수 있으며

원반이 두개인 경우 3번만에 이동시킬 수 있으며

원반이 세개인 경우 7번만에 이동시킬 수 있으며

원반이 네개인 경우 15번만에 이동시킬 수 있다.

 

이런 경향성을 갖는 이유는 맨 아래의 원반을 움직이는데 필요한 이동 횟수는

그 원반을 제외한 위의 원반을 움직이는 횟수이므로 CalculateMoves(n - 1)번이 필요하다.

그 후에 맨 아래의 원반을 움직이는데 1회가 필요하고

다시 그 원반을 제외한 위의 원반을 움직이는데 CalculateMoves(n - 1)번이 필요하므로

n개의 원반을 움직이는데 필요한 횟수는 (2 *  CalculateMoves(n - 1) + 1)번이 필요하다.

 

 

각 움직임을 추적하기 위한 코드를 작성하면 아래와 같은데

 

static void Move(int n, int from, int to, int via)
{
    if (n == 1)
    {
        moves.AppendLine($"{from} {to}");
    }
    else
    {
        Move(n - 1, from, via, to);

        moves.AppendLine($"{from} {to}");

        Move(n - 1, via, to, from);
    }
}

 

Move함수에는 원반의 개수 n, 시작점 from, 목표점 to, 중간점 via를 사용하였으며

원반의 개수가 1개인 경우 바로 목표점을 갈 수 있으므로 from에서 to로 간다고 적어주고,

그 이상인 경우에는 재귀 함수를 사용하여 

n - 1개의 원반을 form에서 via로 옮긴 후에 via에서 to로 옮겨 주었다.

이는 위에서도 설명하였던 원반을 모두 이동시키는데 맨 아래 원반을 제외한 원반을 중간점에 옮긴 후에

맨 아래의 원반을 목표점으로 옮기고, 그 후에 그 원반을 제외한 원반을 중간점에서 목표점으로 옮기기 때문이다.

 

또, 이를 바로 Console.WriteLine()을 사용하면 시간 초과가 발생하므로 stringbuilder를 사용하였다.