C# 프로그래밍 기초 실습 전자책

C# / .NET 알고리즘과 퀴즈
본 알고리즘 퀴즈 문제는 C#/.NET 개발자를 위한 알고리즘 인터뷰 혹은 C# 프로그래밍을 통한
문제 해결 알고리즘을 연구해 보는데 도움이 되고자 작성되었습니다.


퀴즈 질문


예상답변/설명

Stack을 사용하여 세개의 막대기를 표현하는 자료 구조를 먼저 정의한 후, 디스크를 옮기는 부분을 Recursive 함수를 사용하여 아래와 같이 구현한다. 간단하게 N=3이라 할 때, 첫번째 막대기는 1,2,3 숫자를 갖는 스택구조로 표현할 수 있다. 옮기는 과정을 거꾸로 생각하면, 마지막 과정은 두번째 막대기에 1,2라는 디스크가 있게되고, 3을 첫번째에서 세번째로 옮긴후, 다시 두번째 있는 2개의 디스크를 세번째로 옮기게 된다. 두번째의 2개의 디스크를 세번째로 옮기는 것은 다시 한 막대기에서 다른 막대기로 이제 N-1개를 옮기는 것과 동일하므로 Recursive하게 구현될 수 있다.

class HanoiTower
{
    Hashtable ht = new Hashtable();

    public void RunTest()
    {            
        Stack<int> t1 = new Stack<int>(new[] { 3,2,1 });            
        Stack<int> t2 = new Stack<int>();
        Stack<int> t3 = new Stack<int>();
        ht[t1] = "T1";
        ht[t2] = "T2";
        ht[t3] = "T3";

        MoveDisk(t1, t3, t2, t1.Count);
    }

    void MoveDisk(Stack<int> from, Stack<int> to, Stack<int> aux, int n)
    {
        if (n <= 0) return;
        if (n == 1)
        {
            int v = from.Pop();
            to.Push(v);
            Console.WriteLine("Move {0} from {1} to {2}", v, ht[from], ht[to]);
            return;
        }

        MoveDisk(from, aux, to, n - 1);
        MoveDisk(from, to, aux, 1);
        MoveDisk(aux, to, from, n - 1);
    }        
}

Hashtable은 해법을 출력하기 위해 각 스택의 이름을 붙이기 위해 보조적으로 사용되었다.