[백준 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처럼 노드의 깊이가 끝나는 지점(차수가 가장 높은 지점)에서 로그를 찍는다.
- 재귀 동작원리를 완벽하게 이해해야지만 풀기 쉬운 문제인 것 같았다...