[C#/프로그래머스] 하노이의 탑

저 이거푸는데 2일걸렸어요

하노이의 탑 이름 들어본 사람도있을거고 안들어봤어도 퀴즈푸는 게임 해봤다면(레이튼같은게임이나, 학창시절에) 보면 아는 게임이다.

기본적으로 하나의 기둥에 큰 원반부터 작은 원반 순서대로 쌓여있고 이 원반을 그대로 목표하는 기둥(코테기준 3번째 기둥)에

옮기면 되는 문제

 

1. 한번에 한 원반만 옮길 수 있다.
2. 큰 원반은 작은 원반 위에 올릴 수 없다.
3. 최소횟수로 경로를 반환할 것.

 

 

 

 

((저는 이거 푸는데 2일 걸렸습니다. 누가 코테 풀때 1시간 이상 걸리면 그냥 답지 보는게 낫다고 했는데 그냥..

갑자기 자존심?싸움이 되어서 최대한 인터넷 검색 안함. 메모장이랑 하노이 탑 게임 이틀 내내 하면서 패턴 분석 함.

무엇보다 그냥 답지봐도 내가 이해 못하는 이상 정답이 머리에 안들어 올 것 같기도 했습니다.))

 

이러면서 발견한 하노이의 탑을 푸는 몇가지 방법을 알아냈다.

모든 규칙이 코테를 풀기 위한 코드를 짜는 것에 도움이 되지는 않지만.....

 

공통:

1 2 3 타워가 원형 구조라고 가정한다.

1. 가장 위에 있는 고리(사이즈가 1이라고 가정) 1은 걸려 있는 고리의 수가 홀수인지 짝수인지에 따라
1을 탑3에 걸지 탑2에 걸지 결정된다.
2. 세개의 탑중 한 탑이 비어있다면 맨 왼쪽에 있는 고리를 넣어준다.
3. 1은 고리의 수가 홀수인지 짝수인지에 따라 내려가던가 올라간다.(홀수일경우 2로 내려감 짝수일 경우 3으로 올라감)
4. 3탑이 다 차있다면 탑 맨위에 걸려있는 고리 기준으로 중간값을 가장 큰 수에 올린다.
5. 1은 갈길 간다.
6. 탑이 비어있는지 확인 하고 내려놓기 or 고리 합치기

가장 처음에 생각한 알고리즘

이 때문에 코드로 만들때 타워를 다 stack로 만들생각을 했었는데 스택3개를 일일히 확인하고 조건은 만들기에 복잡하고 이게 아닌거같다는 생각이 들어서 폐기함.

 

 

총 고리의 수가 홀수인지에 따라서 

1. 홀수일경우 홀수번째 고리는 내려가고 짝수번째 고리는 올라간다.

2. 짝수일 경우 홀수번째 고리는 올라가고 짝수번째 고리는 내려간다.

가장 처음에 짠 코드와 달리 이거로 인간한테 명령시키면 풀수 있다.

하지만 전 코드를 짜야하죠? 

이걸 사용하면 숫자 하나하나를 추적시켜야하는데 엄두가 안났다... AI 시키면 될지도

 

 

최종 알고리즘

총 고리의수가 k라고 가정할 때 5까지 나오는 값들을 다 적어봤다.

넣을 수 있는 값이 1 2 3 밖에없어서 겹치는 패턴이 많아 그냥 보기에는 규칙을 찾기 힘들다.

 

이전에 찾은 규칙들을 토대로 

3개의 타워를 원형구조라 가정한다.
1. 총 고리의 수가 홀수이면 시작이 [1,3] 짝수면 [1,2] 이다.
2. 1은  0 2 4 등 짝수번째에 무조건 움직여 줘야한다.

보다 싶이 짝수번째(0,2,4,6)는 따로 계산할 필요없이 패턴을 알 수있다.

시작 값은 고리의 수가 홀수인지 짝수인지에 따라 정해지니깐 그 이후부터는 끝값이 시작값이되고 끝값은 시작+1 또는 -1 이 된다.

ex) 12-> 23 or 13 -> 32 -> 21

 

그렇다면 홀수번째 순서들을 어떻게 알아내야할까? 

사진을 보면 앞서 구한 계산식(총고리수 -1)이 그대로 총고리수의 홀수번째에 순서대로 들어간다는 규칙을 볼 수 있다.

 

즉, 내가 구하려는 k의 하노이탑 최소 경로는 이전 k-1의 경로를 알고 있어야만 풀 수 있기 때문에 재귀함수로 풀 수 있다.

1. 총 고리의 수가 홀수이면 시작이 [1,3] 짝수면 [1,2] 이다.
2. 1은  0 2 4 등 짝수번째에 무조건 움직여 줘야한다
3. 홀수번째에는 현재 구하려는 총고리의수-1 의 값을 차례대로 넣어준다.

 

 

using System;

public class Solution
{
    public  int[,] solution(int n)
    {
        int[,] answer = new int[,] { { } };
        answer = fun(n);
        Console.WriteLine(answer.Length);
        return answer;
    }
  
    public  int[,] fun(int num)
    {
        int count = (int)Math.Pow(2, num) - 1;

        int[,] arr = new int[count, 2];
        int[,] prev = new int[count,2];

        if (num==1)
        {
            arr[0,0] = 1;
            arr[0,1] = 3;
            return arr;
        }
        
        prev=fun(num - 1);
      
        bool evenNum = num % 2 == 0 ? true : false;

        int start = 1;
        int end = evenNum ? 2 : 3;

        arr[0, 0] = 1;
        arr[0, 1] = end;

        int prevOrder = 0;
        int row = 1;
        int column = 0;
        for (int i = 1; i < count; i++)
        {
            // 짝수번째일 때
            if (i % 2 == 0)
            {
                //짝수일 때
                if (evenNum)
                {
                    start = end;
                    end = start + 1;
                    if (start > 3) start = 1;
                    else if (end > 3) end = 1;
                }
                else
                {
                    start = end;
                    end = start - 1;
                    if (start < 1) start = 3;
                    else if (end < 1) end = 3;

                }
                arr[row, column] = start;
                column++;
                arr[row, column] = end;

            }//0:0 1:0 2:1 3:1 4:2 5:2
            else
            {
                int a = prev[prevOrder, 0];
                int b = prev[prevOrder, 1];
                arr[row, column] = a;
                column++;
                arr[row, column] = b;
                prevOrder++;
            }
            row++;
            column = 0;

        }
        return arr;
    }   

}

처음에 반환해야할 answer이 이차원 배열로 되어있어서 코드가 쓸데없이 길다!!! 

다른 사람들 보면 List에 int[]를 인자값으로 만들면 코드가 더 깔끔하고 간결해질 것이다. (2차원 배열로 값넣어주다보니 더러워짐)

끝!!!