[BOJ 12906] 새로운 하노이 탑 (Java)

BOJ 12906 새로운 하노이 탑

문제풀이

시간제한 5초, 메모리 512MB 하고싶은거 다 해봐라라는 느낌? 방문체크를 어떻게 할 것인가가 핵심이였다.

• 현재 탑의 상태를 해쉬코드 처럼 하나의 코드로 만들어 set에 저장하는 방식으로 방문체크하였다. 해쉬코드 대신에 statusCode라는 것을 만들어서 현재 탑에 있는 원판의 상태를 그대로 이어 붙혔다.

• 탑을 Stack으로 구현하여 편하게 사용했다.

구현코드

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

public class Main {
	
	static class Node {
		Stack<Character>[] tower;
		
		Node(){
			this.tower = new Stack[3];
			
			for(int i = 0 ; i < 3 ; ++i) {
				this.tower[i] = new Stack<>();
			}
		}

		public String statusCode() {
			String result = "";
			
			for(char c : this.tower[0]) result += c;
			result += '/';
			for(char c : this.tower[1]) result += c;
			result += '/';
			for(char c : this.tower[2]) result += c;
			
			return result;
		}
	}
	
	static HashSet<String> set;
	static Queue<Node> q;
	static String answer;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		set = new HashSet<>();
		q = new LinkedList<>();
		
		int a, b, c;
		a = b = c = 0;
		
		// 데이터 입력받아 초기 상태 만들기 
		Node start = new Node();
		for(int i = 0 ; i < 3 ; ++i) {
			st = new StringTokenizer(br.readLine());
			if(st.nextToken().equals("0")) continue;
			
			for(char ch : st.nextToken().toCharArray()) {
				if(ch == 'A') a++;
				if(ch == 'B') b++;
				if(ch == 'C') c++;
				start.tower[i].push(ch);
			}
		}
		
		// 정답 상태 만들기 
		Node end = new Node();
		for(int i = 0 ; i < a ; ++i) end.tower[0].push('A');
		for(int i = 0 ; i < b ; ++i) end.tower[1].push('B');
		for(int i = 0 ; i < c ; ++i) end.tower[2].push('C');
		
		answer = end.statusCode();
		
		// BFS 들어가기 
		q.offer(start);
		set.add(start.statusCode());
		System.out.println(bfs());
	}

	private static int bfs() {
		int times = 0;
		
		while(!q.isEmpty()) {
			int size = q.size();

			for(int i = 0 ; i < size ; ++i) {
				Node now = q.poll();
				
				// 원판이 모두 제자리를 찾아갔으면 리턴 
				if(now.statusCode().equals(answer)) {
					return times;
				}
				
				// 원판을 옮길 수 있는 모든 경우 
				for(int from = 0 ; from < 2 ; ++from) {
					for(int to = 0 ; to < 3 ; ++to) {
						if(!now.tower[from].isEmpty()) {
							Node next = copy(now);
							
							next.tower[to].push(next.tower[from].pop());
							String statusCode = next.statusCode();
							if(!set.contains(statusCode)){
								set.add(statusCode);
								q.offer(next);
							}
						}
						if(!now.tower[to].isEmpty()) {
							Node next = copy(now);
							
							next.tower[from].push(next.tower[to].pop());
							String statusCode = next.statusCode();
							if(!set.contains(statusCode)){
								set.add(statusCode);
								q.offer(next);
							}
						}
						
					}
				}
			}
			times++;
		}
		
		return times;
	}
	
	private static Node copy(Node origin) {
		Node result = new Node();
		
		for(int i = 0 ; i < 3 ; ++i) {
			for(char ch : origin.tower[i]) result.tower[i].push(ch);
		}
		
		return result;
	}
	
}