HANOI4B

Algorithm Focus

• 그래프의 노드 간 최단 경로를 구할 땐, 기본적으로 너비 우선 탐색 고려하기
• 그래프의 암시적 표현 (너비 우선 탐색을 할 경우, 인접 행렬/리스트 등을 통한 그래프의 직접적인 구현 없이도 큐 하나를 이용해 탐색이 가능)
• 그래프의 노드를 효율적으로 + 간단하게 표현하기 (이 문제에서 각 상태를 정수 하나로 나타냄)
• 양방향 너비 우선 탐색을 통한 알고리즘 최적화

문제

하노이의 탑 문제를 풀되, 기둥의 개수가 4개이고, 초기 상태와 마지막 상태가 임의로 주어진다. 초기 상태에서 마지막 상태를 만들기 위해 필요한
최소한의 움직임 수를 구하라.

시간 및 메모리 제한

• 2초
• 64MB

입력

입력의 첫 줄에는 테스트 케이스의 수 C(C<=50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 원반의 총 수 n(1<=n<=12)이 주어집니다.
각 원반에는 작은 것부터 순서대로 1부터 n까지 번호가 매겨져 있습니다. 그 후 네 줄에는 원반들의 사작 상태,
그리고 그 후 네 줄에는 원반들의 끝 상태가 주어집니다. 이때 각 상태는 맨 왼쪽 기둥부터 하나에 한 줄씩 주어지며,
각 줄의 처음에는 해당 기둥에 꽂힌 원반의 수, 그 후로는 기둥에 꽂힌 원반의 번호가 아래에서부터 주어집니다.
입력에 주어진 원반의 배치에서 큰 원반이 작은 원반 위에 꽂혀 있는 경우는 없습니다.

출력

첫 상태에서 끝 상태로 가기 위한 최소 움직임의 수를 출력합니다.

풀이

문제의 접근 자체는 간단했던 것 같다. 하노이 타워의 각 상태를 그래프의 노드로 정의하고, BFS를 통해 임의의 두 노드 간의
최단 경로를 구하면 될 것이다. 여기서 고려해야할 사항은 크게 두가지이다.

1. 그래프의 노드를 어떤 방식으로 표현할 것인가?
2. 일반적인 BFS를 시도했을 때, 제한 시간 내에 풀 수 있는가?

그래프의 노드, 즉 하노이 타워에 원반들이 놓여있는 상태를 나타내기 위해서는 아래와 같은 직관이 필요하다.

각 원반들이 놓여 있는 기둥의 번호만 알면 (놓여있는 순서와 상관없이), 하노이 타워의 상태는 결정된다.

하노이 타워는 기본적으로 큰 기둥이 작은 기둥보다 위에 올 수 없기 때문에 한 기둥에 놓여 있는 원반의 종류만 알면
원반이 놓여 있는 순서로 이미 알고 있게 되는 것이다. 그러므로 하노이 타워의 상태를 최대 24비트(12(원반 개수의 최댓값) * 2비트(기둥의 인덱스 표현))의 정수로 나타낼 수 있다.

아래는 이렇게 표현한 그래프의 노드를 get하고 set하는 함수이다.

    //state에서 index번째 원반이 놓여 있는 기둥의 인덱스를 반호나
    private static int get(int state, int index) {
        return (state >> (index * 2)) & 3;
    }

    //state에서 index번째 원반을 value번째 기둥으로 옮김
    private static int set(int state, int index, int value) {
        return (state & ~(3 << (index * 2))) | (value << (index * 2));
    }

그리고 이를 통해 간단한 BFS 알고리즘을 구상할 수 있다.

    private static int bfs(int numOfCircle, int begin, int end) {
        if(begin == end) return 0;
        Queue<Integer> queue = new LinkedList<>();

        initializeBy(-1);
        queue.offer(begin);
        c[begin] = 0;

        while(!queue.isEmpty()) {
            int here = queue.poll();

            //각 기둥의 맨 위에 있는 원반을 구한다.
            int[] top = {-1, -1, -1, -1};
            for(int i = numOfCircle - 1 ; i >= 0 ; i--) {
                top[get(here, i)] = i;
            }

            //위에서 구한 원반들을 다른 기둥으로 이동시켜 가면서 마지막 상태에 도달했는지 체크
            for(int i = 0 ; i < 4 ; i++) {
                if(top[i] != -1) {
                    for(int j = 0 ; j < 4 ; j++) {
                        if(i != j && (top[j] == -1 || top[j] > top[i])) {
                            int there = set(here, top[i], j);
                            if(c[there] != -1) continue;
                            c[there] = c[here] + 1;
                            if(there == end) return c[there];
                            queue.offer(there);
                        }
                    }
                }
            }
        }
        return -1;
    }

제한시간은?

위 문제에서 우리가 정의한 상태 공간의 크기는 최대 4^12 이고, 노드 하나를 탐색할 때마다 최대 4^2 만큼의 연산을 실행하므로,
이 알고리즘으로 2초 안에 문제를 풀기는 어렵다. 양방향 BFS로 실행시간을 줄여보자!

private static int bidir(int numOfCircle, int begin, int end) {
        if(begin == end) return 0;
        Queue<Integer> queue = new LinkedList<>();

        initializeBy(0);
        queue.offer(begin); c[begin] = 1;
        queue.offer(end); c[end] = -1;

        while(!queue.isEmpty()) {
            int here = queue.poll();

            int[] top = {-1, -1, -1, -1};
            for(int i = numOfCircle - 1 ; i >= 0 ; i--) {
                top[get(here, i)] = i;
            }

            for(int i = 0 ; i < 4 ; i++) {
                if(top[i] != -1) {
                    for(int j = 0 ; j < 4 ; j++) {
                        if(i != j && (top[j] == -1 || top[j] > top[i])) {
                            int there = set(here, top[i], j);

                            /* 단방향 BFS와 다른 부분!! */
                            /* there가 방문한 적이 없는 노드일 경우 */
                            if(c[there] == 0) {
                                c[there] = incr(c[here]);
                                queue.offer(there);
                            }

                            /* 순방향 탐색과 역방향 탐색이 만나는 순간! */
                            else if(sign(c[there]) != sign(c[here])) return Math.abs(c[there]) + Math.abs(c[here]) - 1;
                        }
                    }
                }
            }
        }

        return -1;
    }

유의할 점은 역방향 탐색에서는 거리를 음수로 나타내기 때문에 거리 배열을 -1이 아닌 0으로 초기화해야 하고,
따라서 마지막에 답을 리턴할 때 -1을 한 뒤에 리턴하는 것이다. 이렇게 하면 충분히 시간 내에 문제를 풀 수 있다.