[백준] 11729번: 하노이 탑 이동 순서(재귀, 분할정복)

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

 

11729번: 하노이 탑 이동 순서

코드

import java.util.Scanner;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int count = 0;
	
	/* 
	 * 기둥 A(from)에서 N개의 원반을 기둥 B(other)를 이용하여 기둥 C(to)로 옮기는 알고리즘.
	 * N: 원판의 개수
	 * from: 출발지 - A
	 * other: 출발지도 목적지도 아닌 곳 - B
	 * to: 목적지 - C
	 *  1. 기둥 A에서 N-1개의 원반을 기둥 C를 이용하여 기동 B로 옮긴다.
	 *  2. 기둥 A에서 1개의 원반을 기둥 C로 옮긴다.
	 *  3. 기둥 B에서 N-1개의 원반을 기둥 A를 이용해서 기둥 C로 옮긴다.
	 */
	public static void hanoi(int N, int from, int other, int to) {
		if(N == 0)
			return;
		count ++;
		// n-1개의 원판을 목적지가 아닌 곳(other)로 옮겨놓음.
		hanoi(N-1, from, to, other);	
		
		// 마지막 원판을 목적지로 옮김.
		sb.append(from + " " + to + "\n");
		
		// 목적지가 아닌 곳(other)에 옮겨놓았던 원판들을 목적지로 옮김
		hanoi(N-1, other, from, to);	
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		hanoi(N, 1, 2, 3);
		System.out.println(count);
		System.out.println(sb);
		scan.close();
	}

}

풀이

https://m.blog.naver.com/PostView.nhn?blogId=puri8467&logNo=221440092130&proxyReferer=https%3A%2F%2Fwww.google.com%2F

재귀 함수에 대한 문제로 유명한 하노이의 탑문제를 풀어보았다.

재귀함수가 뭔가요? 라는 좋은 재귀 문제도 있다.

 

일단 하노이 탑 문제의 조건은 다음과 같다.

 1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.

 2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

 

하노이 탑 문제의 원리는 다음과 같다.

https://m.blog.naver.com/PostView.nhn?blogId=puri8467&logNo=221440092130&proxyReferer=https%3A%2F%2Fwww.google.com%2F

위 사진과 같이 N개의 원판이 존재할 때, 

public static void hanoi(int N, int from, int other, int to)

 1. N-1 개의 원판을 두 번째 칸(중간지점)으로 이동한다.

  -> hanoi(N-1, from, to, other)

 2. 가장 마지막에 남은 원판 1개를 세 번째 칸(목적지)으로 이동한다.

  -> move(from, to)

 3. 두 번째 칸(중간지점)에 존재하는 N-1개의 원판을 세 번째 칸(목적지)으로 이동한다.

  -> hanoi(N-1, other, from, to)

 

위 재귀함수는 직관적으로 이해해야 한다.

hanoi(N-1, from, to, other) 

 -> N-1개의 원판을 먼저 목적지가 아닌 곳으로 옮긴다.(N-1개를 from -> other)

 

move(from, to)

 -> N-1개의 원판을 옮겼으면, 가장 마지막 원판이 1개 남으므로, 그 원판을 목적지로 옮긴다.

 

hanoi(N-1, other, from, to)

 -> 이제 목적지가 아닌 곳에 존재하는 N-1개의 원판을 목적지로 옮긴다.(N-1개를 other -> to)

 

 

https://brenden.tistory.com/31

 

 

https://shoark7.github.io/programming/algorithm/tower-of-hanoi

 

팩토리얼 함수를 보자.

5! = 5*4*3*2*1 이다.

즉 5! = 5 * 4! 과 동일하다.

이 말은, n! = n * factorial(n-1) 과 동일한데, 4!을 재귀를 통해 factorial(n-1)로 호출한다.

public class Main {
	
	public static int factorial(int n) {
		if(n == 1)
			return 1;
		else {
			return n * factorial(n-1);
		}
	}

	public static void main(String[] args) {
		int n = 5;
		int result = factorial(n);
		System.out.println(result);
	}
}

https://gomguard.tistory.com/111

 

 

 

 

1 ~ n까지의 합을 보자.

1 ~ n까지의 합은 n + (1 ~ n-1까지의 합) 과 동일하다.

즉, 1 ~ n-1까지의 합을 재귀를 통해 factorial(n-1)을 호출한다.

public class Main {
	
	public static int factorial(int n) {
		if(n == 1)
			return 1;
		else {
			return n + factorial(n-1);
		}
	}

	public static void main(String[] args) {
		int n = 10;
		int result = factorial(n);
		System.out.println(result);
	}
}

 

 

● 기타 추가 설명

 

하노이의탑 문제의 이해를 위한 보충설명

https://www.codeit.kr/community/threads/7681

 

하노이탑 퍼즐을 쉽게 푸는 해법

https://puzzlemuseum.tistory.com/443

 

 

 

★★★하노이의 탑 이해하기

https://shoark7.github.io/programming/algorithm/tower-of-hanoi