[Java] 백준 10026번: 적록색약

문제

일단 생각하기!

• 재귀로 풀어야함은 알았지만 도저히 어떻게 풀어야할지 감이 잡히지 않아 다른 사람의 풀이를 참고했다.. 다시 풀어보고 이해를 마쳤다!
• 1번 장대에서 3번 장대로 모든 원판들을 옮기려면 가장 아래의 원판, 즉 n번째 원판을 3번 장대로 옮겨야하므로 다른 장대(=2번 장대)로 나머지 원판들을 옮겨놔야 한다. 이 부분은 hanoi(n - 1, from, other, to);로 구현할 수 있다. from은 출발 장대, to는 도착 장대, other는 출발, 도착 장대도 아닌 나머지 장대다.
• 문제의 요구에 따라 from과 to를 출력한 뒤 n번째 장대를 3번째로 옮겨야하므로 hanoi(n - 1, other, to, from);과 같이 구현했다.
• 기저조건은 n이 0일때다!

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 
 * [문제] 백준 11729번 하노이 탑 이동 순서
 * [아이디어] 재귀를 이용한 풀이
 * 가장 작은 원판을 1, 가장 큰 원판을 n이라 할 때, 1부터 n-1까지는 도착 기둥, 즉 3번 기둥이 아닌 다른 기둥으로 옮겨야 한다.
 * n-1번째 원판까지 옮기고 나서는 도착 기둥으로 원판들을 옮겨야 한다.
 * 원판들을 옮길때마다 시간 단축을 위한 StringBuilder에 넣어주고 count를 세준다. 
 * 
 * 메모리 : kb
 * 실행 시간 : ms
 * 
 * @author 김유나
 * 2023-08-31
 * 
 */
public class Main {
	static int count = 0;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()); // 원판 개수
		
		// 원판 개수, 출발 기둥, 도착 기둥, 임시 기둥
		hanoi(n, 1, 3, 2);
		System.out.println(count);
		System.out.println(sb);
	}
	
	static void hanoi(int n, int from, int to, int other) {
		// 기저조건
		if (n == 0) return;
		
		count++;
        // n-1번째 원판까지는 도착 장대가 아닌 다른 장대로 일단 옮겨놔야 한다.
		hanoi(n - 1, from, other, to);
		sb.append(from).append(" ").append(to).append("\n");
        // n 이상의 원판부터에서는 다른 장대에서 도착 장대로 옮겨야 한다.
		hanoi(n - 1, other, to, from);
	}
}