[백준][C#] 11729 하노이 탑 이동 순서 - 실버1

문제 보기

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

11729번: 하노이 탑 이동 순서

 

문제

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

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

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

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

 

 

입력

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

 

 

출력

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

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

 

 

 

코드는 쉽지만 생각해내는 과정이 엄청나게 힘든 문제였다.

심지어 답을 본 뒤에도 이해하는데 오랜 시간이 걸렸다.

그래서 나름대로 쉽게 풀어 설명해보려고 포스팅한다.

 

 

우선 작은 것부터 시작해보자!

 

 

 

시작에 앞서 탑에 이름을 붙여주자.

// 맨 왼쪽 탑부터 0, 1, 2로 정의하자.
// 옮기기 전 탑
int start = 0;

// 옮길 탑
int end = 1;

// 남은 탑
int blank = 2;

이동해야 하는 위치, 시작하는 위치는 항상 바뀌기 때문에

정수값또한 계속 바꿔 넣을 것이다.

 

 

 

 

원판이 1개 있을 때는 어떻게 될까?

 

 

 

// 0번 탑에서 2번 탑으로 이동해야 하기 때문
start = 0;
end = 2;
blank = 1;

 

 

 

 

원판이 2개 있을 때는 어떻게 될까?

 

 

우선 이번엔 우리가 옮겨야 하는 원반에 이름을 붙이자.

 

// 원반의 수를 n이라 할 때
// 제일 큰 원반을 n
// 그 다음으로 큰 원반을 n-1 ...
// n-2, n-3, n-4, n-4 ...

 

// 원반 n - 1을 0번 탑에서 1번으로 이동
index = n - 1;
start = 0;
end = 1;
blank = 2;

// 원반 n을 0번 탑에서 1번으로 이동
index = n;
start = 0;
end = 2;
blank = 1;

// 원반 n - 1을 1번 탑에서 2번으로 이동
index = n - 1;
start = 1;
end = 2;
blank = 0;

 

3개 이후로는 생각하지 않아도 괜찮다.

1개, 2개에서 찾은 규칙으로 생각해본다.

 

원반 1개일 때

1. 원반n을 0에서 2로 이동

 

원반 2개일 때

(원반 n을 이동할 수 없다. 우선 n-1를 이동할 필요가 있다.)

1. 원반n-1을 0에서 1로 이동

2. 원반n을 0에서 2로 이동

3. 원반n-1을 1에서 2로 이동

 

원반 2개인 경우를 그대로 함수를 만들어보자.

void HanoiTop(int n, int start, int end, int blank)
{
	// 원반이 1개일 때는?
    // 바로 end로 이동했다.
    if (n == 1)
    {
        stringBuilder.AppendLine(start + " " + end);
        return;
    }

	// 우선 n-1원반을 이동시켰다.
    // 다만 0에서 1로 이동시켰기 때문에 blank와 end위치를 바꾼다.
    HanoiTop(n - 1, start, blank, end);
    // 위에 있는 원반을 이동시켰으니 n원반을 이동.
    stringBuilder.AppendLine(start + " " + end);
    // n-1원반을 end탑으로 (2번 탑으로) 이동.
    HanoiTop(n - 1, blank, end, start);
}

 

원반이 3개일 경우에도 문제없이 작동되는 것을 확인할 수 있다.

 

총 이동 수는 count를 더해줘도 가능하나,

구하는 규칙을 알아보자.

 

이동하는 원반의 번호를 보면 바로 알 수 있을 것이다.

 

원반이 1개일 때

n

 

원반이 2개일 때

n - 1

n

n - 1

 

원반이 3개일 때

n - 2

n - 1

n - 2

n

n - 2

n - 1

n - 2

 

n 1번 = 2^0

n - 1 2번 = 2^1

n - 2 4번 = 2^2

총 이동 수는 2^3 - 1이다.

 

3번일 경우 2^3 - 1인 것이니,

n으로 뒀을 경우, 2^n -1번일 거라고 도출할 수 있다.

 

코드 보기

static void Main(string[] args)
        {
            using var reader = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            int n = int.Parse(reader.ReadLine());

            StringBuilder stringBuilder = new StringBuilder();
            
            HanoiTop(n, 1, 3, 2);

            print.WriteLine((int)Math.Pow(2, n) - 1);
            print.WriteLine(stringBuilder.ToString());

            void HanoiTop(int n, int start, int end, int blank)
            {
                if (n == 1)
                {
                    stringBuilder.AppendLine(start + " " + end);
                    return;
                }

                HanoiTop(n - 1, start, blank, end);
                stringBuilder.AppendLine(start + " " + end);
                HanoiTop(n - 1, blank, end, start);
            }
        }