[재귀] 하노이 탑 이동 순서

11729번: 하노이 탑 이동 순서 (acmicpc.net)

11729번: 하노이 탑 이동 순서

 

 

->  ArrayList로 담아서 출력했더니, 시간 초과 -> StringBuilder로 시간 초과 문제 해결

 

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	static int answer=0;
	static StringBuilder sb;
	
	public static void main(String[] args) {

		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		sb=new StringBuilder("");
		move(N,1,3);
		
		System.out.println(answer);
		System.out.println(sb.toString());
		
	}
	
	static void move(int n, int x, int y) {
		answer++;
		if(n>1) 
			move(n-1,x, 6-x-y);
		
		sb.append(x+" "+y+"\n");
		
		if(n>1)
			move(n-1,6-x-y,y);
	}

}

 

 

 

 

 

 

 

 

 

 

 

• n-1개의 원판은 시작 기둥에서 임시 기둥으로 이동 
• n번째 원판은 시작 기둥에서 목적지 기둥으로 이동 
• n-1개의 원판을 임시 기둥에서 목적지 기둥으로 이동
• if 이동할 원판수= 0  return;

 

 

• x: 출발지 
• y: 목적지 
• 6-x-y: 임시 기둥 

 

 

1 ) 재귀 1

move(N-1, x, 6-x-y): N-1원판을 출발지에서 목적지가 아닌 남은 기둥으로 옮기기

 

2)재귀2

move(N-1, 6-x-y, y): N-1 원판을 남은 기둥에서 목적지로 옮기기