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

 

 

 

재귀를 사용해서 풀 수 있는 문제이다.

 

재귀함수.. 공부하고 있긴 한데 생각하고 구현하기가 참 어렵다..

이렇게 작동하겠지? 라고 작성하는 정도는 어떻게 할 수 있을 것 같은데, 코드의 작동을 하나하나 따라가서 분석하는게 쉽지 않다..

 

재귀는 dfs bfs 백트래킹 등등 여러 알고리즘에 활용되고, 중요한 테크닉이다.

꾸준히 관련된 문제 풀어보고 공부해서 익숙해져야겠다.

 

 

 

import java.util.*;
import java.io.*;
 
public class Main {
 
	static StringBuilder sb;
 
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		int N = Integer.parseInt(br.readLine());

		sb = new StringBuilder();
 
		sb.append((int)Math.pow(2, N) - 1).append('\n');
 
		Hanoi(N, 1, 2, 3);

		System.out.println(sb);
 
	}

 
	public static void Hanoi(int N, int from, int by, int to) {
		if (N == 1) {
			sb.append(from + " " + to + "\n");
			return;
		}
 
		Hanoi(N - 1, from, to, by);
    
		sb.append(from + " " + to + "\n");
    
		Hanoi(N - 1, by, from, to);
 
	}
}