프로그래머스 문제풀이 (알고리즘) - 하노이 탑

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

코딩테스트 연습 - 하노이의 탑

 

규칙

 

하노이 탑에는 규칙이 있습니다.

n개의 하노이탑을 옮기는데에 M번 움직여야 한다면

n + 1 개의 하노이탑을 움직이는데에 n 개의 하노이탑을 M번 움직여 온전히 이동시키고

가장 큰 원판을 움직인 뒤 다시 n 개의 원판을 M번 이동시킵니다.

즉, n + 1 개의 하노이탑을 온전하게 이동시키기 위한 최소 회수를 M[n + 1] 이라고 하면

M[n + 1] = 2 * M[n] + 1

위 공식이 성립합니다.

 

위 그림과 같이 하노이탑이 있다고 가정하면

3층탑 (7번 움직임)  => [1,3], [1,2], [3,2], [1,3], [2,1], [2,3], [1,3]

이렇게 움직입니다.

1층 짜리부터 4층 짜리까지 모두 움직여 봅니다.

1층탑 (1)  => [1,3]
2층탑 (3)  => [1,2], [1,3], [2,3]
3층탑 (7)  => [1,3], [1,2], [3,2], [1,3], [2,1], [2,3], [1,3]
4층탑 (15) => [1,2], [1,3], [2,3], [1,2], [3,1], [3,2], [1,2], [1,3],[2,3],[2,1],[3,1],[2,3],[1,2],[1,3],[2,3]

 

한편 기둥에 1, 2, 3 이라는 번호를 매겼는데 번호가 아니라 a, b, c 라는 이름을 매기고 위 경로 의미를 다음과 같이 부여 하겠습니다.

a => 출발지 기둥
b => 여분의 기둥
c => 목적지 기둥

그럼 아래와 같이 변경할 수 있습니다.

1층탑  => [a, c]
2층탑  => [a, b] [a, c] [b, c]
3층탑  => [a, c] [a, b] [c, b] [a, c] [b, a] [b, c] [a, c]
4층탑  => [a, b] [a, c] [b, c] [a, b] [c, a] [c, b] [a, b] [a, c] [b, c] [b, a] [c, a] [b, c] [a,b] [a, c] [b, c]

규칙성이 보이시나요?

안보인다면 다음 그림을 참고해주세요.

3개의 원판을 옮겨야 하는 입장 입니다. 다음과 같은 방법으로 원판을 옮깁니다.

 

 

2개의 원판을 여분의 기둥인 b 로 옮긴다 (1번 과정)

가장 큰 원판을 최종 목적지인 c 로 옮긴다 (2번 과정)

나머지 2개의 원판을 목적지 c로 옮긴다 (3번 과정)

여기서 1번 과정과 3번 과정을 보면 다음과 같이 간편화 할 수 있습니다.

 

1번 과정 단순화

2개의 원판을 여분의 기둥인 b 로 옮기는 과정을 단순화 합니다.

가장 큰 3번째 원판은 위 2개를 b로 옮기는 동안 전혀 움직일 수 없으며, 이 과정을 전부 마친 뒤에야 c로 이동할 기회가 주어집니다.

2개의 작은 원판을 옮기는 과정을 단순화 하면 위 그림 처럼 표시가 될 수 있습니다.

여기서 주의할 점은 a에서 c로 옮기는 것이 아니라, 큰 원판을 c로 옮길 수 있도록 위의 2개의 원판을 b로 옮겨야 한다는 것 입니다

즉, 위 그림의 입장에서 c가 목적지가 아니라 b가 목적지 입니다.

목적지를 가장 오른쪽으로 옮기면 다음과 같이 표시할 수 있습니다.

 

• 출발지는 변경 사항이 없다.
• 여분의 기둥이 목적지가 된다.
• 목적이 였던 기둥은 여분의 기둥이 된다.

 

 

3번 과정 단순화

3번 과정은 다음과 같은 상황이 었습니다.

b 에 있는 2개의 기둥 입장에서 목적지는 c 이며 출발지는 b가 됩니다

따라서 다음과 같이 단순화 할 수 있습니다.

• 여분의 기둥이었던 곳은 출발지가 된다.
• 출발지는 여분의 기둥이 된다.
• 목적지는 변화 없다.

 

 

 

만약 n 개의 하노이탑을 목적지로 이동시키는 경로를 path[n] 이라고 하면 다음과 같은 공식이 성립합니다.

( 화살표는 변경 되었음을 시사합니다. 예를 들어서 a → b 라는 표시가 있다면 현재 출발지가 목적지가 되었음을 의미 합니다)

[a, c] 는 a에서 c 로 이동함을 의미합니다. ⇒ 가장 큰 원판의 이동입니다.

 

path[n] = (b→c, c→b)path[n - 1] + [a, c] + (b→a, a→b)path[n - 1]

1층탑 => [a, c]
2층탑 => [a, b] [a, c] [b, c]

즉, 위와 같은 경로를 다음과 같이 변경할 수 있습니다.

path[1] = [a, c]
path[2] = [a, b] [a, c] [b, c]

path[2] 경로는 다음과 같이 구했다고 할 수 있습니다.

path[2] = (b→c, c→b)path[1] + [a, c] + (b→a, a→b)path[1]
path[2] = (b→c, c→b)[a, c] + [a, c] + (b→a, a→b)[a, c]
path[2] = [a,b] [a, c] [b, c]

마찬가지로 path[3] 도 구할 수 있습니다.

path[3] = (b→c, c→b)path[2] + [a, c] + (b→a, a→b)path[2]
path[3] = (b→c, c→b)([a, b] [a, c] [b, c]) + [a, c] + (b→a, a→b)([a,b] [a, c] [b, c])
path[3] = [a, c] [a, b] [c, b] [a, c] [b, a] [b, c] [a, c]

위에서 직접 손으로 그려놨던 경로와 같은지 확인을 해볼까요?

1 => [a, c]
2 => [a, b] [a, c] [b, c]
3 => [a, c] [a, b] [c, b] [a, c] [b, a] [b, c] [a, c]
4 => [a, b] [a, c] [b, c] [a, b] [c, a] [c, b] [a, b] [a, c] [b, c] [b, a] [c, a] [b, c] [a,b] [a, c] [b, c]

완전히 일치하는 것을 볼 수 있습니다.

 

위와 같은 내용을 코드로 옮기면 다음과 같습니다.

단, 코드에서는 [a,b],[a,c] 배열 =>"abac" 을 하나의 문자열로 만들어서 사용했습니다.

 

풀이

public class Solution {
    public int[][] solution(int n) {

        // a : 출발지 => 1
        // b : 여분의 기둥 => 2
        // c : 목적지 => 3
        String hanoi = "ac";
        int last = 1;
        for (int i=2; i<=n; i++) {
            last += last + 1;
            // 처음 출발할 때는 여분의 기둥이 목적지로 보면 이전 경로와 동일하게 움직일 수 있다.
            hanoi = changeRestAndDestination(hanoi) + "ac" + changeRestAndStart(hanoi);
        }

        int[][] answer = new int[last][];
        char[] top = hanoi.toCharArray();
        for (int i=0; i<last; i++) {
            answer[i] = new int[]{top[2 * i] % 96, top[2 * i + 1] % 96};
        }

        return answer;
    }

    public String changeRestAndDestination(String target) {
        char[] box = {'a', 'c', 'b'};
        StringBuilder sb = new StringBuilder();

        for (char c : target.toCharArray())
            sb.append(box[c % 97]);
        return sb.toString();
    }

    public String changeRestAndStart(String target) {
        char[] box = {'b', 'a', 'c'};
        StringBuilder sb = new StringBuilder();

        for (char c : target.toCharArray())
            sb.append(box[c % 97]);
        return sb.toString();
    }

}

짧은 풀이

 public class Solution {
 	public int[][] solution(int n) {
        String hanoi = "ac";
        int last = 1;
        for (int i=2; i<=n; i++, last += last + 1)
            hanoi = change(hanoi, 0) + "ac" + change(hanoi, 1);

        int[][] answer = new int[last][];
        char[] top = hanoi.toCharArray();
        for (int i=0; i<last; i++)
            answer[i] = new int[]{top[2 * i] % 96, top[2 * i + 1] % 96};

        return answer;
    }

    public String change(String target, int t) {
        char[][] box = {{'a', 'c', 'b'}, {'b', 'a', 'c'}};

        StringBuilder sb = new StringBuilder();

        for (char c : target.toCharArray())
            sb.append(box[t][c % 97]);
        return sb.toString();
    }
}