(알고리즘 스터디) (Programmers) 하노이의 탑 🏰

🌟 프로그래머스 / Level2 / 하노이의 탑

📃 문제

프로그래머스

🚫 제한 사항

• n은 15이하의 자연수입니다.

👀 입출력 예

n	result
2	[ [1,2], [1,3], [2,3] ]

🤔 풀이 방법

1️⃣ 탑 이동 규칙 파악 하기

➡️ 탑을 이동시키는 과정을 아래 3단계로 나누어보았다.

① 가장 큰 원판 외 나머지를 다른 곳으로 옮긴다.
② 가장 큰 원판을 3번 기둥으로 옮긴다.
③ 과정 ① 에서 옮겨두었던 원판들을 3번 기둥으로 옮긴다.

➡️ 또 몇개를 나열해보니 요구되는 이동 수가 2의 n제곱 등비수열의 합 형태로 나아가는 것을 알 수 있었다.

① 원판이 1개 일 때 : [ [1,2] ] ➡️ 1번 이동
② 원판이 2개 일 때 : [ [1,2], [1,3], [2,3] ] ➡️ 1+2 = 3번이동
③ 원판이 3개 일 때 : [ [1,2], [1,3], [2,3] ... [2,3] ] ➡️ 1+2+4 = 7번 이동

2️⃣ 사용한 알고리즘 : DFS

➡️ 원판이 이동하는 과정은 아래 그림과 같이 설명할 수 있다.

동작 과정

➡️ 이동 시켜야할 원판의 개수가 1개가 될 때 까지 계속해서 함수들을 호출함으로 DFS 의 형태를 보인다고 할 수있다.

3️⃣ 코드 풀이

➡️ 제일 핵심이 되는 코드는 DFS 를 구현한 부분이 될 것이다.

public static void hanoi(int num, int start, int end) {
    // ①
    if (num == 1) {
        answer[cnt][0] = start;
        answer[cnt][1] = end;
        cnt++;
        return;
    }
    
    // ②
    int sum = start + end;
    int left = 0;

    switch (sum) {
        case 3:
            left = 3;
            break;
        case 4:
            left = 2;
            break;
        case 5:
            left = 1;
            break;
    }
    
    // ③
    hanoi(num -1, start, left);
    hanoi(1, start, end);
    hanoi(num -1, left, end);
}

과정 ① : 이동시켜야할 원판의 개수가 1개라면 시작 기둥 위치에서 목표 기둥 위치로 바로 옮기는 것이 최소 이동일 것이다. 따라서 [start, end] 를 추가해준 뒤 return 해주면 된다.

과정 ② : 앞서 언급한 원판 이동 3단계 중 첫번째 단계에서 어느 기둥으로 나머지 원판을 먼저 이동시켜야할지를 정하기위함이다. 가장 큰 원판의 시작 기둥과 목표 기둥 외 나머지 한 기둥으로 이동해야하기 때문에 합을 바탕으로 해당 기둥을 구했다.

➡️ 다른 해결 방법이 있다면 개선이 필요한 코드인것 같다❗️

과정 ③ : 계속해서 hanoi 함수를 호출하면서 DFS 를 수행한다.

➡️ 괜찮은 속도로 해결했다.

💻 풀이 코드

class Solution {
    public static int[][] answer;
    public static int cnt = 0;
    public int[][] solution(int n) {
        // 배열 초기화
        int total = (int) Math.pow(2, n) - 1;
        answer = new int[total][2];
        
        // 1번에서 3번 원판으로 이동
        hanoi(n, 1, 3);
                
        return answer;
    }
    /*
    int num : 이동해야할 원판의 개수
    int start : 시작 기둥 번호
    int end : 도착 기둥 번호
    */
    public static void hanoi(int num, int start, int end) {
        if (num == 1) { // 옮겨야할 원판이 1개 인 경우 : start, end 삽입 후 리턴
            answer[cnt][0] = start;
            answer[cnt][1] = end;
            cnt++;
            return;
        }
        // 어느 기둥으로 이동할지 결정
        int sum = start + end;
        int left = 0;
        
        switch (sum) {
            case 3:
                left = 3;
                break;
            case 4:
                left = 2;
                break;
            case 5:
                left = 1;
                break;
        }
        
        // 원판 이동 순서 (1) : 마지막 원판을 제외한 나머지 원판을 목표 기둥 외 나머지로 이동
        hanoi(num -1, start, left);
        // 원판 이동 순서 (2) : 마지막 원판을 목표한 위치로 이동
        hanoi(1, start, end);
        // 원판 이동 순서 (3) : 나머지 원판을 목표 위치로 이동
        hanoi(num -1, left, end);
    }
}

 

[level 2] Title: 하노이의 탑, Time: 2.21 ms, Memory: 109 MB -BaekjoonHub · Young998904/Practice_Algorithm_Auto@337ff72