BOJ#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번 장대로 모든 원판을 이동하려면
(... 반복)
* 나의 코드
재귀, 분할정복
bfs + 비트마스크
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));
}
}
'Algorithm > 분할정복' 카테고리의 다른 글
| BOJ#1992 쿼드트리 (0) | 2017.08.25 |
|---|---|
| BOJ#1074 Z (0) | 2017.08.24 |