[프로그래머스][Level2][Java] 하노이의 탑

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12946

프로그래머스

 

풀이코드

public static int[][] answer;
public static int idx;

public static void hanoi(int n, int first, int mid, int last) { //하노이의 탑 알고리즘
    if (n == 0){
        return;
    }
    hanoi(n - 1, first, last, mid);
    answer[idx][0] = first;
    answer[idx++][1] = last;
    hanoi(n - 1, mid, first, last);
}

public static int[][] solution(int n) {
    answer = new int[(int) Math.pow(2, n) - 1][2];      //총 움직인 횟수를 계산해서 answer 배열로 만들어줌
    idx = 0;
    hanoi(n, 1, 2, 3);
    return answer;
}

 

풀이 코드 설명

우선 이 문제는 풀이코드는 간단하지만 이해하기엔 어려울 수도 있다.

우선 하노이의 탑은 위의 그림과 같이 1번 기둥에 있는 원판들을 3번 기둥으로 옮기는 것이다.

단, 여기서 조건은 

1. 한번에 하나의 원판만 옮길 것

2. 큰 원판이 작은 원판의 위에 있으면 안될 것

이렇게 2가지이다.

 

그럼 이 규칙을 지켜서 위의 그림과 같이 원판이 3개일때, 옮기는 것을 보면

1. 제일 큰 원판을 3번 기둥에 옮기고 나서 다른 원판들을 그 위에 쌓아야 되고

2. 다른 원판들은 3번 기둥을 제외한 다른 원판에 대기하고 있다가 3번 기둥에 차례대로 쌓여야 한다. 

그러면 결국 원판들은

이렇게 1번 기둥에서 2번 기둥으로 옮겨진 뒤, 큰 원판이 3번 기둥으로 이동한 후 그 위로 쌓인다.

그럼 여기서 원판 n개를 ?번 기둥에서 ?기둥으로 옮기는 횟수를 hanoi(n)이라고 가정을 하자

 

hanoi(3)을 구하려면 다음과 같은 순서를 거치면 된다.

1. 원판 2개가 1번 기둥 -> 2번 기둥으로 옮겨간다 => hanoi(2)

2. 제일 큰 원판을 1번 기둥 -> 3번 기둥으로 옮긴다. => (+1)

3. 나머지 원판 2개를 2번 기둥 -> 3번 기둥으로 옮겨간다 => hanoi(2)

즉, hanoi(n) = hanoi(n-1)x2 + 1이 된다.

그래서 위의 점화식을 바탕으로 식을 세워서 계산을 하면

hanoi(n) = 2ⁿ-1이라는 식이 나오고 이것을 이용해서

public static int[][] solution(int n) {
    answer = new int[(int) Math.pow(2, n) - 1][2];      //총 움직인 횟수를 계산해서 answer 배열로 만들어줌
    idx = 0;
    hanoi(n, 1, 2, 3);
    return answer;
}

이 코드에서 answer배열의 길이를 지정해주었다.([원판이 움직인 횟수][경로])

여기서 경로는 ?기둥 -> ??기둥이므로 2로 길이를 지정해주었다.

 

그 다음 위와 같은 원리를 이용해서

public static void hanoi(int n, int first, int mid, int last) { //하노이의 탑 알고리즘
    if (n == 0){
        return;
    }
    hanoi(n - 1, first, last, mid);
    answer[idx][0] = first;
    answer[idx++][1] = last;
    hanoi(n - 1, mid, first, last);
}

위의 메서드를 지정했는데

원판이 움직일 때, ?에서 ??기둥으로 움직이려면 바로 원판을 다 옮기진 못하고 어찌됐든 한번은 다른 기둥에서 잠시 놔두고 위에서 설명한 대로 제일 큰 원판이 ??기둥으로 옮겨진 뒤, 나머지 원판들을 옮겨야 하니까

현재 원판들이 있는 기둥 : first

중간에 잠시 놔두는 기둥 : mid

최종적으로 옮길 기둥 : last

이렇게 지정을 하고 위에서 hanoi(n) = hanoi(n-1)x2 +1이라는 원리를 이용해서

hanoi(n, first, mid, last)

= hanoi(n-1, first, last, mid) => 제일 큰 원판을 last로 옮기기 전에 나머지 원판을 우선 mid에 놔둔다.

(예를 들어 first = 1번, mid = 2번, last = 3번이면 제일 큰 원판을 3번으로 옮기기 전에 나머지 원판을

2번으로 잠시 옮길 것이므로 hanoi(n-1)은 최종목적지를 mid로 설정해주는 것이다.)

 

+ 제일 큰 원판을 first -> last로 옮김

answer[idx][0] = first;
answer[idx++][1] = last;

 

+ hanoi(n-1, mid, first, last) => 제일 큰 원판을 last로 옮긴 뒤, 나머지 원판을 mid에서 last로 다 가져온다.

 

그래서 이러한 방식으로 재귀함수를 이용하면 하노이의 탑을 쉽게 풀 수 있다.