[백준/자바] 11729: 하노이의 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

---

하노이의 탑은 쌓아 놓은 원반을 최소 횟수로 옮기기 위한 알고리즘이다.

처음에 모든 원반이 크기가 큰 순서대로 첫 번째 기둥에 쌓여 있고, 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮기는 문제이다. '하노이의 탑' 문제는 대표적인 재귀 알고리즘 문제이다.

 

'하노이의 탑' 알고리즘은 크게 3단계로 나눌 수 있다.

 

1. 바닥의 원반을 제외한 그룹을 시작 기둥에서 중간 기둥으로 이동
2. 바닥의 원반을 시작 기둥에서 목표 기둥으로 이동
3. 바닥의 원반을 제외한 그룹을 중간 기둥에서 시작 기둥으로 이동

원반의 개수에 따라 위 과정이 재귀적으로 실행된다.

 

풀이 코드는 다음과 같다.

public class Boj_11729 {

   static int count = 0;
   static StringBuilder sb = new StringBuilder();

   public static void main(String[] args) throws NumberFormatException, IOException {
       // TODO Auto-generated method stub
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

       int N = Integer.parseInt(br.readLine());
       move(N, 1, 3);
       System.out.println(count);
       System.out.println(sb);
   }

   static void move(int n, int x, int y) {
       if(n>1)
           move(n-1, x, 6-x-y);

       sb.append(x + " " + y + "\n");
       count += 1;

       if(n>1)
           move(n-1, 6-x-y, y);
   }
}

 

* 추가적으로 '하노이의 탑' 문제에서 원판을 옮기는 최소 이동 횟수는 2^n - 1이다.

첫 풀이: StringBuilder 대신 ArrayList에 배열 {x, y}에 넣고, main 함수에서 for문을 통해 출력 -> 시간초과

별 다른 기능 없이 그저 print가 목적이므로 StringBuilder로 수정