[백준] 15500 이상한 하노이 탑 - Java

 

 

 

스택을 사용해서 풀 수 있는 문제이다.

 

기존 하노이 탑에서 조건이 많이 수정돼서 재귀를 사용할 필요가 없다.

 

1 2 3 세 개의 장대가 주어지고, 3번 장대에 탑을 쌓아주면 되는 상황이다.

 

 

1. 1번 장대에 걸린 요소들을 검사해 3번 장대에 들어갈 순서인지 확인하고, 맞으면 3번 아니면 2번으로 옮긴다.

 

2. 2번 장대에 대해서도 위와 같은 작업을 수행한다.

 

3. 3번 장대에 탑이 완성되면 마무리한다.

 

 

 

import java.util.*;
import java.io.*;
 
public class Main {
 
	static StringBuilder sb;
 
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		int N = Integer.parseInt(br.readLine());

		Stack<Integer> st1 = new Stack<>();
		Stack<Integer> st2 = new Stack<>();
		Stack<Integer> st3 = new Stack<>();

		StringTokenizer st = new StringTokenizer(br.readLine());

		StringBuilder sb = new StringBuilder();


		for(int i=0; i<N; i++){	
			st1.add(Integer.parseInt(st.nextToken()));	
		}


		int cnt = 0;
		int target = N;		

		while(true){

			if(st3.size() == N){
				break;
			}


			while(!st1.empty()){
				int temp = st1.pop();
				cnt++;

				if(temp == target){
					st3.push(temp);
					target--;
					sb.append(1 + " " + 3 + "\n");
					if(target == 0){
						break;
					}
				}else{
					st2.push(temp);
					sb.append(1 + " " + 2 + "\n");
				}
			}

			while(!st2.empty()){
				int temp = st2.pop();
				cnt++;

				if(temp == target){
					st3.push(temp);
					target--;
					sb.append(2 + " " + 3 + "\n");
					if(target == 0){
						break;
					}
				}else{
					st1.push(temp);
					sb.append(2 + " " + 1 + "\n");
				}
			}



		} // end of first while

		System.out.println(cnt);
		System.out.println(sb);


		
	}
}