[재귀] 백준 JAVA(자바) #11729 하노이 탑 이동 순서

<문제>

11729번: 하노이 탑 이동 순서

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

 

[입력]

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

[출력]

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

 

---

 

이동 전

위 그림은 원판이 4개인 경우의 예시이다.

위 그림을 아래 그림과 같이 옮겨주는 것이 목표이다.

이동 후

---

<풀이과정>

1. 제일 큰 원판 d를 제외하고 (N-1)개의 원판을 3(장대)를 임시버퍼로 사용하여 1에서 2로 옮겨준다.

harnoi(n-1, 1, 3, 2)

2. 1에 남아있던 d를 3에 옮겨준다.

count += 1

3. 2에 남아있던 (N-1)개의 원판들을 1을 임시 버퍼로 사용하여 2에서 3으로 옮겨준다.

harnoi(n-1, 2, 1, 3)

---

위 풀이과정을 코드로 바꾸면 다음과 같다. 

 

import java.util.Scanner;
 
public class Main {
    private static int result = 0;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int num = sc.nextInt();
        
        harnoi(num, 1, 2, 3);
        System.out.println(result);
    }
 
    //n : 원판의 개수 , from: 시작 장대, tmp: 임시버퍼, to: 이동하고자 하는 장대
    //from = 1, tmp = 2, to = 3
    public static void harnoi(int n, int from, int tmp, int to) {
        result += 1;    //harnoi가 호출될때마다 1증가 = 총 이동 횟수
        
        if(n == 1) {
            System.out.println(from + " " + to);
            return;
        }
        
        harnoi(n-1, from, to, tmp);        //1. (n-1)개를 1에서 2로 이동        
        System.out.println(from + " " + to);    //2. 남아 있던 d원판을 1에서 3으로 이동
        harnoi(n-1, tmp, from, to);        //3. (n-1)개를 2에서 3으로 이동
    }
}
 

※ 위와 같은 방법으로 풀었더니 결과가 원하는대로 나오지 않음

잘못된 결과

 

---

따라서 result가 먼저 나오도록 하기 위해 StringBuilder를 사용해주었다.

import java.util.Scanner;
 
public class Main {
    private static int result = 0;
    private static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int num = sc.nextInt();
        
        harnoi(num, 1, 2, 3);
        System.out.println(result);
        System.out.println(sb);
    }
 
    //n : 원판의 개수 , from: 시작 장대, tmp: 임시버퍼, to: 이동하고자 하는 장대
    //from = 1, tmp = 2, to = 3
    public static void harnoi(int n, int from, int tmp, int to) {
        result += 1;    //harnoi가 호출될때마다 1증가 = 총 이동 횟수
        
        if(n == 1) {
            sb.append(from + " " + to +"\n");
            return;
        }
        
        harnoi(n-1, from, to, tmp);        //1. (n-1)개를 1에서 2로 이동
        sb.append(from + " " + to +"\n");        //2. 남아 있던 d원판을 1에서 3으로 이동
        harnoi(n-1, tmp, from, to);        //3. (n-1)개를 2에서 3으로 이동
    }
}
 

---

<참고자료>
티스토리, "[백준 11729][자바] 하노이 탑 순서", https://jul-liet.tistory.com/112