[알고리즘/C#] 프로그래머스 - 하노이의 탑 (Lv.2, 재귀)

👀 풀이 방법
알고리즘 문제를 풀때마다 느끼는 건데, 알고 있는 개념을 코드로 옮기는게 더 어려운 것 같다.
이번 문제는 이 블로그 글을 참고했다.
핵심은 쌓여있는 탑의 마지막 n번째 판을 목적지로 옮기는 것이다.


n번째 판을 목적지까지 옮겨야 하므로, n-1개를 목적지가 아닌 다른 곳으로 먼저 옮긴다.

그다음 n번째 판을 목적지로 옮기고,

다른 곳에 옮겨뒀던 n-1개도 목적지로 마저 옮겨주면 된다.

결국 n번째 판을 하나씩 옮기는 재귀문제인 것이다.

using System;
using System.Collections.Generic;

public class Solution 
{
    public void Hanoi(int moveCnt, int start, int end, int spare, ref List<(int, int)> answer)
    {
        if (moveCnt == 1)
        {
            answer.Add((start, end));
            return;
        }

        // n-1개를 목적지가 아닌 여분 판으로 옮긴다.
        Hanoi(moveCnt - 1, start, spare, end, ref answer);
        // n번째 판을 목적지로 옮긴다.
        answer.Add((start, end));
        // n-1개도 마저 목적지로 옮긴다.
        Hanoi(moveCnt - 1, spare, end, start, ref answer);
    }

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

        Hanoi(n, 1, 3, 2, ref answer);

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

        return answerArr;
    }
}