[백준 알고리즘][자바] 11729번 : 하노이 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

알고리즘에서 유명한 하노이 탑입니다.

근데 저는 한 번도 접해보지 못한... 부족한 점이 많습니다.

 

단순히 최소 횟수를 출력하는 것이 아닌, 과정까지 출력되어야 하기 때문에 일단 예제부터 살펴보도록 하겠습니다.

입력으로는 원판의 개수가 주어지고

출력으로는 첫째 줄에는 최소 횟수를 출력하고 두 번째 줄부터는 그 과정을 출력합니다.'

 

다음은 원판이 3개 일때 입니다.

1. 1번 장대에서 3번 장대로 이동
2. 1번 장대에서 2번 장대로 이동
3. 3번 장대에서 2번 장대로 이동
4. 1번 장대에서 3번 장대로 이동
5. 2번 장대에서 1번 장대로 이동
6. 2번 장대에서 3번 장대로 이동
7. 1번 장대에서 3번 장대로 이동

처음 원판을 옮길 때, 생각해야 할 점은 1번 장대에 있는 가장 큰 원판을 3번 장대의 제일 밑에 위치시키는 것일 겁니다.

처음 시작을 1번 장대에서 3번 장대로 이동시켰는데, 2번 장대도 비어있는데 굳이 3번 장대로 이동시킨 이유가 있다고 생각했습니다. 뭔가 원판의 개수가 홀수냐 짝수냐에 따라 바뀔 거 같습니다.

 

원판이 4개일 때를 한번 생각해보겠습니다.

 

1. 1번에서 2번 장대로 이동(짝수닌깐 2번으로 해보겠습니다.)

2. 1번에서 3번 장대로 이동

3. 2번에서 3번 장대로 이동

4. 1번에서 2번 장대로 이동

5. 3번에서 1번 장대로 이동

6. 3번에서 2번 장대로 이동

7. 1번에서 2번 장대로 이동 - 장대에 3개의 원판을 옮기는 횟수가 예제 입력과 동일하네요.

8. 1번에서 3번 장대로 이동

9. 2번에서 3번 장대로 이동

10. 2번에서 1번 장대로 이동

11. 3번에서 1번 장대로 이동

12. 2번에서 3번 장대로 이동

13. 1번에서 2번 장대로 이동

14. 1번에서 3번 장대로 이동

15. 2번에서 3번 장대로 이동

총 15번이네요.

1번부터 15번까지 반복해서 보다 보면 규칙이 보입니다.

예제 입력에서 3개의 원판을 옮기는 횟수가 7회입니다.

 

4개의 원판을 옮기는 과정 요약을 하자면 아래와 같습니다.

1. 1번 장대에 깔려있는 4번 원판을 3번 장대로 옮기기 위해서 3개의 원판을 2번 장대에 옮기는 횟수 = 7회
2. 1번 장대에 깔려있던 4번 장대를 3번 장대로 옮기는 횟수 = 1회
3. 다시 2번 장대 있던 3개의 원판을 3번 장대로 옮기는 횟수 = 7회  

N개의 원판을 옮기는데 걸리는 최소 횟수를 M이라고 했을 때를 공식으로 나타내면 아래와 같습니다.

• M = 2 * (N-1개의 원판을 옮기는데 걸리는 횟수) + 1

검증을 해보겠습니다.

1. 1개의 원판을 옮기는데 걸리는 횟수 = 1회
2. 2개의 원판을 옮기는데 걸리는 횟수 = 2 * 1 + 1 = 3회
3. 3개의 원판을 옮기는데 걸리는 횟수 = 2 * 3 + 1 = 7회
4. 4개의 원판을 옮기는데 걸리는 횟수 = 2 * 7 + 1 = 15회

위의 공식을 수학적으로 풀어내면 아래와 같은 공식이 나옵니다.

출처 : 네이버 지식백과

검색을 하시면 자세한 설명을 볼 수 있습니다.

위의 공식을 사용하면 횟수를 바로 구할 수 있지만

개발자라면 모르는 게 정상(?) 이기 때문에 모른다 치고 진행하도록 하겠습니다.

 

2개의 원판을 옮기는 것을 과정으로 풀어내면 아래와 같습니다.

1. 원판(1)을 1에서 2로 이동
2. 원판(2)을 1에서 3으로 이동
3. 원판(1)을 2에서 3으로 이동

이것을 그대로 N개에 대입해보겠습니다.(단, N=1일 때는 1에서 3으로 이동)

1. 원판(N-1)을 1에서 2로 이동
2. 원판(N)을 1에서 3으로 이동
3. 원판(N-1)을 2에서 3으로 이동

 

코드로 풀어낸 과정은 아래와 같습니다.

 

1. N=1일 때는 1에서 3으로 이동

	public static int hanoi(int N, int start, int sub, int to, int count) {
		
		count++; // 메서드가 한번 실행될때마다 1회 옮김
		
		if(N == 1) { // N=1이면 1에서 3으로 이동
			System.out.println(start + " " + to); 
			return count;
		}

		return count;
	}

2. 원판(N-1)을 1에서 2로 이동

	public static int hanoi(int N, int start, int sub, int to, int count) {
		
		count++; // 메서드가 한번 실행될때마다 1회 옮김
		
		if(N == 1) { // N=1이면 1에서 3으로 이동
			System.out.println(start + " " + to); 
			return count;
		}
		
		count = hanoi(N-1, start, to, sub, count); // N-1을 1에서 2로 이동

		return count;
	}

3. 원판(N)을 1에서 3으로 이동

	public static int hanoi(int N, int start, int sub, int to, int count) {
		
		count++; // 메서드가 한번 실행될때마다 1회 옮김
		
		if(N == 1) { // N=1이면 1에서 3으로 이동
			System.out.println(start + " " + to); 
			return count;
		}
		
		count = hanoi(N-1, start, to, sub, count); // N-1을 1에서 2로 이동
		System.out.println(start + " " + to); // N을 1에서 3으로 이동
		
		return count;
	}

4. 원판(N-1)을 2에서 3으로 이동

	public static int hanoi(int N, int start, int sub, int to, int count) {
		
		count++; // 메서드가 한번 실행될때마다 1회 옮김
		
		if(N == 1) { // N=1이면 1에서 3으로 이동
			System.out.println(start + " " + to); 
			return count;
		}
		
		count = hanoi(N-1, start, to, sub, count); // N-1을 1에서 2으로 이동
		System.out.println(start + " " + to); // N을 1에서 3으로 이동
		count = hanoi(N-1, sub, start, to, count); // N-1을 2에서 3으로 이동
		
		return count;
	}

 

 

마지막은 출력을 위한 StringBuilder를 추가한 코드입니다.

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

public class Main {
	
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws NumberFormatException, IOException {

// 		백준 알고리즘 11729번
//		시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
//		1 초	256 MB	45658	22461	17386	48.841%
//		문제
//		세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
//
//		한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
//		쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
//		이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		
		int count = hanoi(N, 1, 2, 3, 0, sb);
		
		bw.write(String.valueOf(count)+"\n");
		bw.write(sb.toString());
		
		br.close();
		bw.flush();
		bw.close();
		
		
	}
	
	public static int hanoi(int n, int start, int sub, int to, int count, StringBuilder sb) {
		
		count++;
		
		if(n == 1) {
			sb.append(start + " " + to + "\n");
			return count;
		}
		
		count = hanoi(n-1, start, to, sub, count, sb);
		sb.append(start + " " + to + "\n");
		count = hanoi(n-1, sub, start, to, count, sb);
		
		return count;
	}
}

 

짝수일 때는 첫 시작이 1->2이고 홀수일 때는 시작이 1->3인 규칙성이

코드에서도 첫 번째 재귀 함수가 실행될 때, to와 sub가 번갈아가면서 실행되는 것으로 나타나지네요.

 

 

이번 문제를 풀면서 느낀 점은 하노이 탑에 대한 공식을 몰라도 count를 해서 횟수를 구하는 것이 개발자스럽다고 생각이 들었네요.