[Algorithm/BOJ] 11729 : 하노이 탑 이동 순서.java (재귀)

문제

https://www.acmicpc.net/problem/11729

 

구현

가장 무거운 원판을 세 번째 장대로 옮겨야 한다는 점과 N개의 원판을 옮기는 과정이 N-1개의 원판을 옮기는 과정을 포함한다는 점까지는 생각해냈는데 재귀 함수 구현에서 GPT의 도움을 받았다.

 

hanoi 함수 구현

static int hanoi(int n, int from, int via, int to) {
		if (n == 1) {
			sb.append(from + " " + to + "\\n");
			stacks[to].push(stacks[from].pop());
			return 1;
		}
}

 

 

 

처음에 n == 1일 경우부터 생각하였다.

이 경우에는 첫 번째 장대에 있는 원판을 최종 장대로 옮기면 끝이므로 위와 같이 작성하였다.

 

 

 

그리고 n == 2일 때의 과정을 직접 읊어보며 어떻게 다음 재귀를 실행할지 고민하였다. 직접 숫자를 대입하니 쉽게 생각할 수 있었다. 두 개의 원판이 있을 때는 일단 첫 번째 장대에서 1를 중간 장대로 옮겨야 하므로 from = 1, to = 2가 되도록 하였다.

hanoi(1, 1, 3, 2);

hanoi(n-1, from, to, via);

그 다음 가장 무거운 원판인 2를 최종 장대로 옮겨야 한다.

stacks[3].push(stacks[1].pop());

// n-1개의 원판들이 모두 옮겨졌고 남은 가장 무거운 원판을 옮겨야 하므로
// 현재 호출된 함수의 매개값 from에서 to로 옮겨야 한다.
stacks[to].push(stacks[from].pop());

 

 

 

마지막으로 중간 장대에 있던 원판 1을 최종 장대로 옮긴다.

hanoi(1, 2, 1, 3);

hanoi(n-1, via, from, to);

 

따라서 n == 2일 때 총 3회의 이동이 필요하다.

 

 

 

n == 3일 경우, 원판이 2개일 때 가운데 장대로 옮기는 과정(3회)과 첫 번째 장대에서 가장 무거운 원판인 3을 최종 장대로 옮기는 과정(1회), 가운데 장대에 있는 원판 2개를 최종 장대로 옮기는 과정(3회)을 반복하여 총 7회의 이동이 필요하다.

위 과정을 통하여 아래와 같이 코드를 작성하게 되었다.

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static Stack<Integer>[] stacks = new Stack[4];
	
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(bf.readLine());
		
		for (int i = 1; i <= 3; i++) stacks[i] = new Stack<>(); // 3개의 스택(장대) 초기화
		
		for (int i = n; i >= 1; i--) stacks[1].push(i); // 첫 번째 장대에 원판 삽입
		
		System.out.println(hanoi(n, 1, 2, 3));
		System.out.println(sb.toString());
	}
	
	static int hanoi(int n, int from, int via, int to) {
		int move = 0;
		
    // 원판 한 개 일때는 from -> to로 이동 후 1 반환
		if (n == 1) {
			sb.append(from + " " + to + "\n");
			stacks[to].push(stacks[from].pop());
			return 1;
		}
		
		
		// 가장 무거운 원판을 제외한 n-1개의 원판들을 중간 장대로 이동
		move += hanoi(n-1, from, to, via);

    // 가장 무거운 원판을 최종 장대로 이동
		sb.append(from + " " + to + "\n");
		stacks[to].push(stacks[from].pop());
		move++;
		
    // 중간 장대에 있던 n-1개의 원판들을 최종 장대로 이동
		move += hanoi(n-1, via, from, to);
		
		return move;
		
	}
}