[백준,BOJ 11729] 하노이 탑 이동 순서(JAVA 구현, 재풀이)

-내 생각

  별 찍기 - 10 문제와 마찬가지로 이전에 풀어봤던 문제로, 당시에는 이해가 불가능해 그냥 공식처럼 외우고자 했었는데, 이번에는 그나마 그 때보다는 좀 더 이해할 수 있었다고 생각되는 문제이다..

 

-해법

  우선 하노이탑의 조건은 탑의 가장 상단에 있는 작은 원판부터 움직일 수 밖에 없게 되어있다. 즉 원판에 번호를 붙혀 생각해본다면, 1번 원판을 우선으로 고려해야 하기 때문에 n이 몇이던지 작은 부분으로 쪼개기 위해 재귀함수를 사용해야 한다. n이 3일 때, 3을 움직일 수 없으므로 -> 2를 고려, 2도 움직일 수 없으므로 -> 1을 고려, 1이 가장 작은 원판이기에 1부터 시작한다. 

 

import java.util.Scanner;

public class Main{
	static int k = 0;
	static StringBuilder sb = new StringBuilder();
	
	static void hanoi(int n, int start, int temp, int des) { // 재귀 함수
		if(n == 1) { // 종료조건, n이 제일 작은 원판이 되었을 때
			k++; // 이동횟수 증가
			sb.append(start+" "+des+"\n"); // 목표 지점에 이동	
			return; // 재귀함수 종료
		}
		
		hanoi(n-1,start,des,temp); // 가장 큰 원판을 목적지에 옮기기 위해 n-1개의 원판을 중간위치에 모두 옮겨야 한다.
		sb.append(start+" "+des+"\n"); // 가장 큰 원판을 목적지에 옮긴다.
		k++; // 이동 횟수 증가
		hanoi(n-1,temp,start,des); // 중간위치의 원판들을 다시 목적지에 옮긴다.
		
	}
	
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        
        int n = in.nextInt(); // 원판의 개수 입력
        
        hanoi(n,1,2,3); // 원판의 개수, 시작지점, 거쳐가는 지점, 목적지점을 123으로 표현해 전달
        
        System.out.println(k); // 옮긴 횟수
        System.out.println(sb); // 이동 경로
        
        in.close();
    }
}