[백준 11729] 하노이 탑 이동 순서

문제

 

풀이

import java.util.Scanner;

public class Main {

	public static int moveCount = 0;
	public static StringBuffer sb = new StringBuffer();
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		scanner.close();
		
		hanoi(1,2,3,n);
		
		System.out.println(moveCount);
		System.out.println(sb.toString());
	}
	
	public static void hanoi(int from, int middle, int to, int n) {
		if (n == 0) return;
		moveCount++;
		hanoi(from, to, middle, n-1);
		sb.append(from + " " + to + "\n");
		hanoi(middle, from, to, n-1);
	}
}

n = 3일때,

1. hanoi(1,2,3,3) 

2. hanoi(1,3,2,2)

3. log: 1 3 // 네번째 로그

4. hanoi(2,1,3,2)

 

// 2번의 재귀

5. (2-1) hanoi(1,2,3,1)

6. (2-2) log: 1 2 // 두번째 로그

7. (2-3) hanoi(3,1,2,1)

 

// 4번의 재귀

8. (4-1) hanoi(2,3,1,1)

9. (4-2) log: 2 3 // 여섯번째 로그

10. (4-3) hanoi(1,2,3,1)

 

// 5번의 재귀

11. (5-1) hanoi(1,3,2,0)

12. (5-2) log: 1 3 // 첫번째 로그

13. (5-3) hanoi(2,1,3,0)

 

// 7번의 재귀

14. (7-1) hanoi(3,2,1,0)

15. (7-2) log: 3 2 // 세번째 로그

16. (7-3) hanoi(1,3,2,0)

 

// 8번의 재귀

17. (8-1) hanoi(2,1,3,0)

18. (8-2) log: 2 1 // 다섯번째 로그

19. (8-3) hanoi(3,2,1,0)

 

// 10번의 재귀

20. (10-1) hanoi(1,3,2,0)

21. (10-2) log: 1 3 // 일곱번째 로그

22. (10-3) hanoi(2,1,3,0)

 

- 재귀함수 호출시, 재귀가 중단되기 전까지(n == 0일 때 중단)는 다음 실행 코드로 넘어가지 않는다.

- DFS처럼 노드의 깊이가 끝나는 지점(차수가 가장 높은 지점)에서 로그를 찍는다.

 

- 재귀 동작원리를 완벽하게 이해해야지만 풀기 쉬운 문제인 것 같았다...

 

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