백준 11729. 하노이 탑 이동 순서

www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

문제제목 : 하노이 탑 이동순서

문제난이도 : 실버2

문제유형 : 재귀

 

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

 

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

 

코드

package week2;

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

public class BOJ11729_하노이탑 {
	
	public static StringBuilder sb = new StringBuilder();
	
	public static void hanoiTop(int n, int start, int mid, int to) {
		if (n == 1) {
			sb.append(start + " " + to + "\n");
			return;
		}
		
		//n-1을 b로 이동
		hanoiTop(n - 1, start, to, mid);
		
		//1개(n번)을 c로 이동
		sb.append(start + " " + to + "\n");
		
		//n-1을 b에서 c로 이동
		hanoiTop(n - 1, mid, start, to);
	}
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		sb.append((int) (Math.pow(2, n) - 1) + "\n");
		hanoiTop(n, 1, 2, 3);
		System.out.println(sb);
	}
}

 

아이디어

(0) A에 있는 n개의 원반을 C로 옮겨야한다. (Hanoi(n))

(1) 가장 큰 원반을 C로 옮기기 위해서 A에 있는 n-1개를 B로 이동시킨다. (Hanoi(n-1))

(2) 남은 가장 큰 원반을 C로 이동한다. (+1회)

(3) B에 남은 n-1개의 원반을 C로 옮겨야한다. (Hanoi(n-1))

 

결국 이동 횟수는 2 x Hanoi(n-1) + 1 이라는 걸 알 수 있다.

1개 원판은 1회

2개 원판은 3회

3개 원판은 7회

...

총 횟수는 2^n - 1이다.

 

총 횟수는 알았으니 이제 원판이 어느 장판에서 어느 장판으로 이동하는지를 알아내야한다.

원판 이동이 시작하는 장판은 start, 중간 장판은 mid, 마지막 최종으로 이동해야하는 장판은 end라고 표현을 하겠다.

먼저 시작은 Hanoi(n, 1, 2, 3)

가장 큰 원반을 end로 이동하기 위해서는 n-1개의 원판을 mid로 이동해주어야한다.

Hanoi(n-1, 1, 3, 2)

1번 장판에 남은 1개의 원판을 3번으로 이동해준다.

pring(1 -> 3)

다시 2번 장판에 남은 n-1개의 원판을 최종 3번 장판으로 이동해주어야한다.

Hanoi(n-1, 2, 1, 3)

추가학습

수학관련 클래스 Math 클래스!!!

Math는 조만간 메소드들을 정리해서 글을 올릴 예정이다! 

오늘은 먼저 하노이탑 문제를 해결하는데 사용한 Math.pow()에 대해 추가 학습을 할 것이다.

Math.pow(double a, double b) 는 a의 b승을 반환한다. double형을 가지고 제곱연산을 수행하기때문에 정수가 되기위해선 형변환이 필요하다. 따라서 문제에서도 (int) Math.pow(2, n)으로 작성하여 형변환을 해주었다.

 

*시간복잡도

n을 입력 시, n, n-1, n-2, n-3, ...., 1 이므로 n번 반복하게되는 재귀함수이다.

따라서 시간복잡도는 O(n)이다.