[백준] 11729 하노이 탑 이동 순서 - 재귀 JAVA

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

11729번: 하노이 탑 이동 순서

코드설명

재귀를 활용하는 문제입니다.

 

하노이 탑 문제입니다.

위의 문제를 풀기 위해서 이해해야할점은,

1. 1번 탑에서 2번탑으로 가장 큰 탑 1개가 남을때까지 모두 2번탑으로 이동시킵니다.

2. 가장큰 원판을 3번 탑으로 이동시킵니다.

3. 2번탑에서 3번탑으로 이동시킵니다.

 

위의 로직을 이해하고 재귀를 활용하면 풀 수 있습니다.

자세한 설명은 주석으로 달아두었습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int N;
	public static int answer = 0;
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	System.out.println( (1 << N ) -1 );
    	simulate(N, 1, 3); //N개의 원판을 1 에서 3으로 이동시킨다.
    	System.out.println(sb.toString());
	}
	
	public static void simulate(int cnt, int from, int to) {
		//1에서 2로 간다면, middle값은 3 이다.
		//1에서 2으로 간다면, middle값은 2이다.
		//2에서 1 로 간다면, middle값은 3 이다.
		//2에서 3으로 간다면, middle값은 1 이다.
		//3에서 1로 간다면, middle값은 2이다.
		//3에서 2로 간다면, middle값은 1 이다.
		int middle = 6 - from - to; 
		
		if(cnt == 1) { //종료조건. 만약 1개를 옮기려면 바로 from 에서 to로 이동시킵니다.
			sb.append(from+" "+to).append("\n");
			return ;
		}
		if(cnt >= 2) { //2개를 옮긴다면, 아래의 방법으로 움직이게 할 수 있다. 
			simulate(cnt - 1, from , middle); //가장 큰 원판 뺴고 모두 middle 하노이 탑으로 이동시킵니다.
			simulate(1, from, to); //가장 밑판은 3번쨰 탑으로 이동시킵니다.
			simulate(cnt - 1, middle, to); //2번째 하노이 탑에서 3번쨰 하노티압으로 모두 이동시킵니다.
		}
	}

}