[백준 11729 Java] 하노이 탑 - 재귀, 분할 정복

분할 정복이란?

한 번에 해결하기 어려운 문제를 해결 가능한 단위로 나누고,

작은 문제들을 해결한 후 합쳐서 큰 문제를 해결하는 방법

 

 

아래 하노이 탑 예제를 보고 이를 적용해보자.

 

* 원판의 개수가 2개, 3개라고 생각하고 그림을 그리면 이해가 빠를 것이다.

결국에는 같은 루트로 원판들이 옮겨지는 것이라고 생각하면 된다.

 

* String 대신에 StringBuilder를 사용해서 탐색 속도를 빠르게 했다.

단순한 알고리즘에서는 큰 차이가 없지만 복잡해질수록 차이가 나므로 StringBuilder 사용에 익숙해지자.

 

 

import java.util.Scanner;

public class Ex4 {
	
	static StringBuilder sb = new StringBuilder(); // 이동 순서가 담길 배열
	static int cnt = 0; // 이동 횟수
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		hanoi(n, 1, 2, 3); // 막대기 세 개를 순서대로 1, 2, 3으로 지정해줌
		
		System.out.println(cnt);
		System.out.println(sb);
		
	}
	
	// 원판의 개수(n), 출발지(1), 경유지(2), 목적지(3)
	public static void hanoi(int n, int start, int mid, int to) {

		cnt++; // 이동 횟수 증가
		
		// 이동할 원반의 수가 1개라면
		if(n == 1) {
			sb.append(start + " " + to + "\n"); // 바로 1번에서 3번으로 이동해라.
			return;
		}
		
		// 이동할 원판의 수가 1개가 아닐 때
		
		// 첫째: n-1개를 1번에서 2번으로 이동 (그래야 1번 맨 아래에 있는 원판이 3번으로 가지)
		// 과정: 1번의 원판들을 3번 막대기를 이용해서 2번으로 옮기자. 그래야 3번이 비니까. 
		hanoi(n-1, start, to, mid); // 따라서, 1->3->2 순서가 됨
		
		// 둘째: 1번에 남아있는 제일 큰 원판을 1번에서 3번으로 이동
		sb.append(start + " " + to + "\n");
		
		// 셋째: n-1개를 2번에서 3번으로 이동 (이제 얘네들도 목적지로 보내주자)
		// 과정: 2번에 남아있는 원판들을 1번을 이용해서 3번으로 옮겨주자. 
		hanoi(n-1, mid, start, to); // 따라서, 2->1->3 순서가 됨
		
	}
	
}

 

완벽하게 이해가 된 문제가 아니라 재귀에 대해 좀 더 익숙해지고 문제를 다시 풀어보자!