백준 11729 하노이 탑 (Gold V) [C#]

11729번: 하노이 탑 이동 순서

 

문제

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

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

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

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

 

 

 

풀이 방법

힌트1

가장 아래의 원판을 3번째로 옮기려면 어떻게 해야할까?

당연하게도 다른 모든 원판을 2번째로 옮겨야 한다.

 

지금 보니까 전부 1로 해놨네요..

 

즉, 가장 큰 원판을 제외한 다른 원판을 중간 지점으로 보내는 것이 핵심이다

 

 

 

힌트2

위 상황에서 3번으로 모두 옮기는 로직

1. 원판3을 3번으로 옮기려면 원판2를 2번으로 옮겨야한다.

2. 원판2를 2번으로 옮기려면 원판1을 3번으로 옮겨야한다.

3. 원판1은 3번으로 옮길 수 있으니 출력해준다 (1->3)

4. 원판2를 2번으로 옮길 수 있게 되었으니 출력해준다 (1->2)

5. 원판3을 3번으로 옮기려면 원판1을 2번으로 옮겨줘야한다

6. 원판1을 2번으로 옮길 수 있으니 출력해준다 (3->2)

7. 원판3을 3번으로 옮길 수 있으니 출력해준다 (1->3)

8. 원판2를 3번으로 옮기려면 원판1을 1번으로 옮겨야한다

9. 원판1을 1번으로 옮길 수 있으니 출력해준다 (2->1)

10. 원판2를 3번으로 옮길 수 있으니 출력해준다 (2->3)

11. 원판1을 3번으로 옮길 수 있으니 출력해준다 (1->3)

 

아까말한 중간지점이 여기서의 옮겨야한다가 됨

 

힌트3

public static void Hanoi(int n,  int from, int by, int to)
{
    if (n == 0)
        return;

    Hanoi(n - 1, from, to, by);
    sb.AppendLine($"{from} {to}");
    Hanoi(n - 1, by, from, to);
}

1. from에서 to로 가기 위해서 위의 원판(n-1)을 중간지점(by)로 옮겨줘야한다.   [Hanoi(n - 1, from, to, by);]

2. if(n == 0) 이라면 위의 원판이 없다는 이야기니 중간지점을 생략하고 목표 지점(to) 옮겨줄 수 있다.   [sb.AppendLine($"{from} {to}");]

3. 중간 지점에에 보낸 원판을 다시 목표 지점(to)로 옮겨준다    [Hanoi(n - 1, by, from, to);]

 

 

 

 

정답 코드

using System;
using System.Collections.Generic;
using System.ComponentModel.Design;
using System.IO;
using System.Runtime.CompilerServices;
using System.Text;

namespace Alroghtim_CS
{
    class Program
    {
        static StringBuilder sb = new StringBuilder();


        public static void Hanoi(int n,  int from, int by, int to)
        {
            if (n == 0)
                return;

            Hanoi(n - 1, from, to, by);
            sb.AppendLine($"{from} {to}");
            Hanoi(n - 1, by, from, to);
        } 

        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            Console.WriteLine(Math.Pow(2, N) - 1);

            Hanoi(N, 1, 2, 3);
            Console.Write(sb.ToString());
        }
    }
}

 

StringBuilder를 사용하지 않고 바로바로 출력해주면 시간초과가 발생함

백준 C# 속도 개선