BOJ#11729 하노이 탑 이동 순서

BOJ#11729 하노이 탑 이동 순서

* 문제

https://www.acmicpc.net/problem/11729

* 풀이

<BFS + 비트마스크>

처음에는 bfs + 비트마스크를 이용하여 풀었습니다.

하노이탑의 각 상태를 비트마스크를 이용하여 long 정수 하나로 구현하고, bfs 탐색을 해가면서 목표 정점을 찾는 방식

(각 원판은 3개의 장대 중 하나에 존재할 수 있으므로 원판의 위치는 2비트로 표현할 수 있습니다.)

그러나 정점의 최대 개수가 3^20이고, 각 정점마다 3^2 loop를 통해 탐색을 하므로

총 시간복잡도 3^22로 시간초과 발생합니다.

,

<분할 정복법>

- 분할 정복법 : 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결하고, 그 결과들을 합병하면서 본 문제를 해결하는 방식

- 단점 : 보통 재귀 방식으로 구현되는데, 재귀 함수 호출 오버헤드가 부담된다면 다른 방식으로도 구현할 수 있다.

원판이 N개일 때, 1번 장대에서 3번 장대로 모든 원판을 이동하려면

  1) N-1개의 원판을 2번 장대로 모두 옮긴다.

  2) 하나 남은 원판을 3번 장대로 옮긴다.

원판이 N-1개일 때,  2번 장대에서 3번 장대로 모든 원판을 이동하려면

(... 반복)

---

* 나의 코드

재귀, 분할정복

https://github.com/stack07142/BOJ/blob/master/BOJ%2311729_HanoiTower/src/Main.java

bfs + 비트마스크

https://github.com/stack07142/BOJ/blob/master/BOJ%2311729_HanoiTower/src/Main2.java

import java.io.*;

/**
 * BOJ#11729 하노이 탑 이동 순서
 * https://www.acmicpc.net/problem/11729
 */

public class Main {

    static BufferedReader br;
    static BufferedWriter bw;

    public static void main(String[] args) throws IOException {

        int N;

        // input
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        // solve
        bw.write((int) Math.pow(2, N) - 1 + "\n");

        solve(N, 1, 3);

        bw.flush();

        bw.close();
        br.close();

    } // ~ main

    static void solve(int N, int from, int to) throws IOException {

        if (N == 0) return;

        solve(N - 1, from, 6 - from - to);
        bw.write(from + " " + to + "\n");
        solve(N - 1, 6 - from - to, to);
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 * BOJ#11729 하노이 탑 이동 순서
 * https://www.acmicpc.net/problem/11729
 *
 * bfs + 비트마스크로 최소 이동 횟수 구하기
 */

public class Main2 {

    static final int EMPTY = -1;

    public static void main(String[] args) throws IOException {

        int N;              // 원판의 개수
        long state = 0L;    // 현재 상태
        long endState = 0L; // 목표 상태
        HashSet<Long> discovered = new HashSet<>(); // 정점 중복 방문 처리

        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        // 장대는 0번부터 2번까지 있다 (3개)
        // 원판은 0번부터 N-1번까지 있다 (N개)

        // 목표 상태 : 모든 원판이 2번 장대에 있는 경우
        for (int i = 0; i < N; i++) {

            endState <<= 2;
            endState |= 2;
        }

        // solve - bfs
        int cnt = -1;
        Queue<Long> queue = new LinkedList<>();

        queue.add(state);
        discovered.add(state);

        while (!queue.isEmpty()) {

            cnt++;

            int size = queue.size();
            for (int i = 0; i < size; i++) {

                long curState = queue.poll();

                // 종료조건
                if (curState == endState) {

                    System.out.println(cnt);
                    return;
                }

                // 게임판 변환
                // 각 장대의 Top에 위치한 원판(Piece)을 구한다
                int[] top = {EMPTY, EMPTY, EMPTY};
                for (int j = N - 1; j >= 0; j--) {

                    top[(int) get(curState, j)] = j;
                }

                // 탐색
                // j번 장대의 top을 k번 장대로 옮긴다
                for (int j = 0; j < 3; j++) {
                    for (int k = 0; k < 3; k++) {

                        // 두 장대가 같은 경우
                        if (j == k) continue;
                        // j번 장대에 원판이 없는 경우
                        if (top[j] == EMPTY) continue;

                        // j번 장대의 top이 k번 장대의 top보다 큰 경우
                        if (top[k] != EMPTY && top[j] > top[k]) continue;

                        long nextState = set(curState, top[j], k);

                        // 이미 방문한 정점인 경우
                        if (discovered.contains(nextState)) continue;

                        queue.add(nextState);
                        discovered.add(nextState);
                    }
                }
            }
        }

    } // ~ main

    static long get(long state, int index) {

        // (index)번 원판의 위치를 반환
        return (state >> (index * 2)) & 3;
    }

    static long set(long state, int index, int value) {

        // (index)번 원판의 위치를 지우고 -> (index)원판의 위치를 value로 기록한다
        return (state & ~(3 << (index * 2))) | (value << (index * 2));
    }
}