C# 하노이의 탑 - 재귀 / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/12946

 

 

나의 풀이

public int[,] solution(int n) 
{
    var list = new List<(int, int)>();

    Hanoi(list, n, 1, 3, 2);

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

    return answer;
}

private void Hanoi(List<(int, int)> list, int n, int start, int end, int sub)
{
    if(n == 1) 
    {
        Move(list, start, end);
        return;
    }

    Hanoi(list, n - 1, start, sub, end); // 맨 밑판 빼고 sub로 이동한다.
    Move(list, start, end); // 맨 밑판을 타겟지점으로 옮긴다.
    Hanoi(list, n - 1, sub, end, start); // 처음에 옮겼던걸 이제 다시 타겟지점으로 옮긴다.
}

private void Move(List<(int, int)> list, int start, int end)
{
    list.Add((start, end));
}

재귀 배울때 배우는 대표 문제인 하노이의 탑.

직관적으로 식을 알 수 있는 피보나치 수열과 달리 하노이의 탑은

n - 1을 수행할때마다 쌓여있는 탑의 위치가 바뀌기 때문에 주의해야한다.