문제 링크
문제
오늘은 새로운 하노이 탑 게임을 해보려고 한다. 이 게임의 규칙은 다음과 같다.
-
막대는 총 세 가지 종류가 있다. 막대 A, 막대 B, 막대 C
-
게임이 시작될 때, 각각의 막대에는 0개 또는 그 이상의 원판이 놓여져 있다.
-
모든 원판의 크기는 같으며, 원판의 종류도 A, B, C로 세 가지가 있다. 원판은 원판 A, 원판 B, 원판 C와 같이 표현한다.
-
한 번 움직이는 것은 한 막대의 가장 위에 있는 원판을 다른 막대의 가장 위로 옮기는 것이다.
-
게임의 목표는 막대 A에는 원판 A만, 막대 B는 원판 B만, 막대 C는 원판 C만 놓여져 있어야 한다.
-
되도록 최소로 움직여야 한다.
막대 A, 막대 B, 막대 C에 놓여져 있는 원판의 상태가 주어졌을 때, 게임의 목표를 달성하는데 필요한 움직임의 최소 횟수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 막대 A에 놓여져 있는 원판의 개수와 막대 A의 상태, 둘째 줄에 막대 B에 놓여져 있는 원판의 개수와 막대 B의 상태, 셋째 줄에 막대 C에 놓여져 있는 원판의 개수와 막대 C의 상태가 주어진다. 막대의 상태는 밑에 있는 원판부터 주어진다.
각 막대의 상태는 A, B, C로만 이루어진 문자열이며, 모든 막대에 놓여져 있는 원판 개수의 합은 1보다 크거나 같고, 10보다 작거나 같다.
출력
게임의 목표를 달성하는데 필요한 움직임의 최소 횟수를 출력한다.
알고리즘: BFS, 해시를 사용한 집합과 맵
풀이
원판 개수의 합은 1보다 크거나 같고, 10보다 작거나 같다. 즉 이 정도 범위면 중복 없이 원판이 움직이는 모든 경우의 수는 부담이 되지 않는 수다.
솔루션은 간단하다. 현재 하노이 상태에서 A -> B,C로 원판을 움직이는 경우, B -> A,C로 원판을 움직이는 경우, C -> A,B로 원판을 움직이는 경우를 게임의 목표를 달성할 때까지 탐색해주면 된다. -> (먼저 목표를 달성한 노드는 움직인 횟수가 최소인 노드이다. 움직임은 너비마다 +1 해준다.)
솔루션은 간단하지만, 구현에서 조금 애먹은 문제다. 내가 구현한 방법은
ArrayList<ArrayList>를 이용해서 하노이 상태를 저장했고, 방문 처리는 hashMap<String, Boolean>을 이용했다. ex) key -> list.get(0).toString() + list.get(1).toString() + list.get(2).toString();
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static char hanoi[] = {'A', 'B', 'C'};
static ArrayList<ArrayList<Character>> start = new ArrayList<>();
static HashMap<String, Boolean> visited = new HashMap<>();
static int ans;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for(int i=0; i<3; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
start.add(new ArrayList<>());
if(Integer.parseInt(st.nextToken()) != 0) {
String input = st.nextToken();
for(int j=0; j<input.length(); j++) {
start.get(i).add(input.charAt(j));
}
}
}
BFS();
System.out.println(ans);
}
static void BFS() {
Queue<ArrayList<ArrayList<Character>>> que = new LinkedList<>();
que.add(start);
visited.put(combine_str(start), true);
int cout = 0;
while(que.size()!=0) {
int sz = que.size();
for(int i=0; i<sz; i++) {
ArrayList<ArrayList<Character>> n = que.poll();
if(hanoi_check(n)) {
ans = cout;
return;
} else {
for(int j=0; j<3; j++) {
for(int k=0; k<3; k++) {
if(n.get(j).size() != 0) {
if(j!=k) {
ArrayList<ArrayList<Character>> next_n = arrayList_clone(n);
move(next_n, j, k);
String key = combine_str(next_n);
if(visited.get(key) == null) {
que.add(next_n);
visited.put(key, true);
}
}
}
}
}
}
}
cout += 1;
}
}
static ArrayList<ArrayList<Character>> arrayList_clone(ArrayList<ArrayList<Character>> list) {
ArrayList<ArrayList<Character>> clone = new ArrayList<>();
for(int i=0; i<3; i++) {
clone.add(new ArrayList<>());
clone.get(i).addAll(list.get(i));
}
return clone;
}
static void move(ArrayList<ArrayList<Character>> list, int from, int to) {
list.get(to).add(list.get(from).get(list.get(from).size()-1));
list.get(from).remove(list.get(from).size()-1);
}
static String combine_str(ArrayList<ArrayList<Character>> list) {
StringBuilder sb = new StringBuilder();
for(int i=0; i<3; i++) {
sb.append(list.get(i).toString());
}
return sb.toString();
}
static boolean hanoi_check(ArrayList<ArrayList<Character>> list) {
for(int i=0; i<3; i++) {
for(int j=0; j<list.get(i).size(); j++) {
if(list.get(i).get(j) != hanoi[i]) return false;
}
}
return true;
}
}