[백준/JAVA] 11729번 하노이 탑 이동 순서

• 재귀적인 패턴을 찾아서 재귀함수로 찍는 문제
  https://www.acmicpc.net/problem/11729

1. 문제

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

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
   이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

2. 문제 접근

1) 원판의 개수 N을 입력받는다.
2) Hannoi 함수를 이용하여 원판을 옮긴 횟수와 이동 순서를 구한다.
3) 옮긴 횟수와 이동 순서를 출력한다.

• Hannoi 함수
• 원판의 갯수와 시작 위치, 목적지, 마지막으로 이동 순서를 입력할 StringBuilder를 매개변수로 받는다.
• 원판이 한개일 경우 옮긴 횟수를 1 증가시키고 이동 순서로 시작 위치와 목적지를 추가시킨다.
• 원판이 한개가 아닐 경우 Hannoi(원판의 갯수 -1, 시작위치, 목적지가 아닌 다른곳, StringBuilder)를 통해 가장 밑에 원판을 제외한 위의 원판들을 목적지가 아닌 다른곳으로 옮긴다.
• 가장 마지막 원판을 목적지로 옮기기 위해 옮긴 횟수를 1 증가시키고 이동 순서로 시작 위치와 목적지를 추가시킨다.
• 후에 Hannoi(원판의 갯수 -1, 목적지가 아닌 다른곳, 목적지, StringBuilder)를 통해 아까 옮겨 놓은 원판들을 다시 목적지로 옮긴다.

3. 코드

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

public class Main {
    static int K;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        Hannoi(N, 1, 3, sb);
        System.out.println(K);
        System.out.print(sb);
    }

    static void Hannoi(int n, int start, int dest, StringBuilder sb) {
        if(n==1) {
            sb.append(start).append(" ").append(dest).append("\n");
            K++;
            return;
        }
        Hannoi(n-1, start, 3-(start+dest)%3,sb);
        sb.append(start).append(" ").append(dest).append("\n");
        K++;
        Hannoi(n-1, 3-(start+dest)%3, dest, sb);
    }
}