(Java)백준 11729. 하노이 탑 이동 순서

1. 문제 조건

어릴 때 많이 해보던 하노이탑!! 내가 정말 좋아하던 놀이였다 ,, 그냥 내가 알고 있던 하노이탑 규칙 그 자체 ! 

원판을 옮긴 총 개수와 옮긴 과정(원판이 원래 있던 위치 원판을 옮긴 목적지)를 각각 순차적으로 출력해야 했다.

 

2. 아이디어

하노이 수열의 점화식을 외워본 적이 없어서 하노이 수열의 규칙부터 찾아봐야 했다. 많은 관찰과 고민을 거듭한 끝에 점화식을 찾았고, 하노이를 옮기는 과정에 전체 솔루션 내에 작은 솔루션들을 구분할 수 있게 됐다. 알고리즘 스터디원들에게 웹엑스로 필기하며 설명해준 과정도 아래 첨부한다. 내가 사고한 과정을 최대한 그대로 설명해주려고 노력했다. 

규칙을 찾아간 과정은 우선, 원판 개수에 따라서 이동 과정이나 하노이 수를 관찰하고 그 과정에서 규칙성을 발견하는 방식으로 해결방법에 접근했다.

그러고 보니, 제일 큰 원판을 옮길 때를 제외하고 앞 뒤로 바로 직전과 직후에 n-1개의 원판을 옮겨야 한다는 규칙을 발견할 수 있었다.

 

3. 구현

package Silver1;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main_11729하노이탑이동 {
	//N일 때마다 옮긴 횟수를 저장해 둘 배열
	static int[] numbers = new int[21];
	
	
	static StringBuilder sb = new StringBuilder();
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		int N = Integer.parseInt(br.readLine());
		sb.append(hanoiNum(N)).append("\n");
		hanoiMove(N,1,3);
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	//하노이 옮긴 횟수를 계산하여 반환하는 메서드
	static int hanoiNum(int n) {
		if(n==1)	{
			if(numbers[n] ==0 ) {
				numbers[n]=1; 
			}
			return 1;
		}
		if(numbers[n]==0) {
			numbers[n] = hanoiNum(n-1)*2 +1;
			return numbers[n];
		}
		return numbers[n];

	}
	//n개의 원판을 a에서 b로 이동시킬 때의 과정을 bw에 저장하는 메서드
	static void hanoiMove(int n, int a, int b) {
		//시작지점
		int start = a;
		//목적지
		int destination = b;
		//임시값
		int temp =0;
		//(시작,도착지)에 따라 임시위치 설정
		if((start==1 && destination ==3)||(start==3 && destination ==1)) temp =2;
		if((start==2 && destination ==3)||(start==3 && destination ==2)) temp =1;
		if((start==1 && destination ==2)||(start==2 && destination ==1)) temp =3;
		
		//옮길 판의 개수가 1개일 때는 바로 시작지점에서 목적지로 옮기기
		if(n==1) {
			sb.append(start).append(" ").append(destination).append("\n");
			return;
		}
		
	
		//맨 처음에 짝수든 홀수든 첫번째 
		if(n>1) {
			hanoiMove(n-1, start, temp);
			sb.append(start).append(" ").append(destination).append("\n");
			hanoiMove(n-1, temp, destination);
			return;
		}
	}

}