[프로그래머스 Programmers] 하노이의 탑

문제 설명

하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.

• 한 번에 하나의 원판만 옮길 수 있습니다.
• 큰 원판이 작은 원판 위에 있어서는 안됩니다.

하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.

1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.

 

제한사항

n은 15 이하의 자연수입니다.

 

프로그래머스

 

 

하노이의 탑 이해하기

'하노이의 탑(Tower of Hanoi)'은 프랑스의 수학자 에두아르 뤼카가 1883년에 소개한 문제이다.

아래 그림으로 표현할 수 있다.

 

이때 원반을 옮기는 몇 가지 조건이 따른다.

 

• 한 번에 움직일 수 있는 원반은 기둥 위에 놓인 원반 하나뿐이다.
• 어떤 원반 위에 그보다 더 큰 원반을 쌓을 수 없다.

 

이 조건 하에서 '최소의 이동 횟수로 옮기는 가짓수'를 구하거나, '최소 이동횟수로 옮길 때 각 원반을 이동하는 순서'등을 구하는 것이 하노이의 탑 문제가 된다.

 

아이디어 얻기

어떻게 아이디어를 포착할까? 어떤 알고리즘 문제라도, 감각적으로 아이디어가 안 떠오를 때 가장 먼저 시도해 볼수 있는 것은, 실제로 하나씩 해보는 것이다. 이 문제에서는 실제로 원반을 하나씩 옮겨보는 것이다.

중요한 것은, 문제를 작게 축소해서 시도해서 해결해보고, 그것을 확대하는 것이다.

 

한번 해보자. 우선 Hanoi(3)으로 시작해보자. 그리고 나서 얻은 통찰을 확인해보자.

 

 

3번 형태를 유심히 볼 필요가 있습니다. Hanoi(2)도 직접 해본다면 해당 형태가 동일하게 나타나는걸 알 수 있습니다.

그리고 더 나아가서 3번 형태는 B 기둥으로 실행된 Hanoi(2)으로 볼 수 있습니다.

 

규칙을 발견한 하노이의 탑

Hanoi(1) = Hanoi(0) + 1번 원반

Hanoi(2) = Hanoi(1) + 2번 원반

Hanoi(3) = Hanoi(2) + 3번 원반

....

= Hanoi(n) = Hanoi(n -1) + n번 원반

 

이를 재귀를 이용해서 작성하면 문제가 해결될거 같습니다.

규칙에 따라 3번째 원반을 A에서 C로 옮기려면 위의 두 원반은 'B'에 이미 꽂혀있어야한다. 즉, 이때 hanoi(2)가 필요하다고 보여진다. 위 그림의 4번째 움직임에서도 2개의 원반을 'B'에 꽂은 후 3번째 원반은 'C'로 옮겼다. 이제 2개의 원반을 'B'에서 'C'로 옮겨야 한다. 여기서도 hanoi(2)가 필요하다.

 

Hanoi(3) = Hanoi(2) + 3번째 원반 이동 + Hanoi(2)로 구성된다는걸 확인

 

풀이 코드

using System;
using System.Collections.Generic;

public class Solution {
    public int[,] solution(int n)
    {
        List<(int, int)> answer = new List<(int, int)> ();
        HanoiTower(n, 1, 3, 2, answer);

        int[,] array = new int[answer.Count, 2];

        for (int i = 0; i < answer.Count; i++)
        {
            array[i, 0] = answer[i].Item1;
            array[i, 1] = answer[i].Item2;
        }

        return array;
    }

    public void HanoiTower(int n, int start, int target, int middle, List<(int, int)> answer)
    {
        if (n == 1)
        {
            answer.Add((start, target));
            return;
        }

        HanoiTower(n - 1, start, middle, target, answer);
        answer.Add((start, target));
        HanoiTower(n - 1, middle, target, start, answer);
    }
}

 

참조 사이트

'하노이의 탑' 이해하기 (feat. 재귀 함수)