하노이 탑 이동 순서 [재귀 함수, 6단계, 11729번, C#]

11729번: 하노이 탑 이동 순서

문제

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

 

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

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

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

 

입력

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

출력

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

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

 

참고

하노이의 탑 이해 및 재귀를 활용하여 풀기

 

풀이

우선 첫 번째 입력부터 작성하겠습니다. 첫째 줄에 쌓일 원판의 개수를 입력받습니다.

static int InputNumber(string input)
{
    int number = int.Parse(input);
    return number;
}

그럼 출력부분을 살펴보겠습니다.

 

출력의 결과물은 위 모습과 같아야합니다.

 

코드 작성에 앞서 원반이 2개일때와 3개일때의 경우를 살펴보겠습니다.

 

이렇게 2개일때는 총 3단계면 원반을 다 옮길 수 있습니다. 3개인 경우도 살펴보겠습니다.

 

3개일때도 마찬가지로 똑같이 3단계면 됩니다. 크게 보면요. 가장 밑바닥 원을 목표 지점에 보기 위해서 3단계를 가집니다. 이걸 재귀로 표현하면 이렇게...

 

똑같은 방식으로 이루어집니다. ... 이렇게 역순으로 원반이 두개인 경우의 결과를 가지고 3개인 경우의 원반옮기기를 풀고 이 결과를 가지고 4개의 경우를 풀고 이런 느낌입니다. 

 

using System;
using System.Text;

namespace _191009_backjoon_hanoi {
    class Program {
        static void Main(string[] args)
        {
            int disks = InputNumber(Console.ReadLine()); //원반 갯수 입력
            Console.WriteLine(Math.Pow(2,disks)-1); //총 이동 횟수

            StringBuilder sb = new StringBuilder();
            SolveHanoi(sb, disks, 1, 3); 
            Console.WriteLine(sb.ToString());
        }

        static void SolveHanoi(StringBuilder sb, int disks, int fromPeg, int toPeg)
        {
            //탈출 조건
            if (disks == 0)
                return;

            int sparePeg = 6 - fromPeg - toPeg;

            //재귀 조건
            SolveHanoi(sb, disks - 1, fromPeg, sparePeg);
            sb.AppendFormat("{0} {1}\n", fromPeg, toPeg);
            SolveHanoi(sb, disks - 1, sparePeg, toPeg);
        }

        static int InputNumber(string input)
        {
            int number = int.Parse(input);
            return number;
        }
    }
}

코드입니다... 하노이 탑 총 이동 횟수는 등비수열의 공식을 통해 풀 수 있습니다. 그리고 더 저렴한 스트링 빌더를 사용했습니다. 그 외 등등 자세한 설명은 하지 않겠습니다. 저도 이해가 잘 안가서 결국 구글링해서 검색해봤습니다.

 

여기서 중요하고 이해하기 어려운 지점이 int sparePeg 인 듯 합니다. 나머지 기둥을 의미하는데요. 나머지 기둥을 어떻게 찾아낼거냐가 중요한 포인트같습니다.

 

지금보면 코드는 다 이해가 가지만, 이걸 아무것도 모른 상태에서 어떻게 풀수있을까 감히 생각도 못하겠습니다 ㅎㅎ;; 참 어렵습니다--;;