하노이의 탑

문제

문제 풀이

using System;
using System.Collections.Generic;

public class Solution 
{
    public int[,] solution(int n) 
    {
        List<int[]> resultList = new List<int[]>();
        
        // 1에서 3으로 n개의 원반을 옮긴다.
        // 1 : 출발 기둥
        // 3 : 목표 기둥
        // 2 : 보조 기둥
        Hanoi(n, 1, 3, 2, resultList); 
        
        // List<int[]>를 int[,]로 변환
        int[,] result = new int[resultList.Count, 2];
        for (int i = 0; i < resultList.Count; i++)
        {
            result[i, 0] = resultList[i][0];
            result[i, 1] = resultList[i][1];
        }

        return result;
    }
    
    public void Hanoi(int n, int from, int to, int aux, List<int[]> resultList)
    {
        if (n == 1)
        {
            resultList.Add(new int[] { from, to }); // 이동 경로 기록
            return;
        }

        // n-1개의 원반을 보조 기둥(aux)으로 옮긴다.
        Hanoi(n - 1, from, aux, to, resultList);

        // 가장 큰 원반을 목적지로 옮긴다.
        resultList.Add(new int[] { from, to }); // 이동 경로 기록

        // n-1개의 원반을 목적지로 옮긴다.
        Hanoi(n - 1, aux, to, from, resultList);
    }
}