[백준] 11729번 - 하노이 탑 이동 순서 [Java]

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

 

[백준] 11729번 - 하노이 탑 이동 순서 [Java]

[백준] 11729번 - 하노이 탑 이동 순서 [Java]

---

1.  아이디어

 

재귀 함수와 StringBuilder를 활용하면 해결할 수 있다.

---

2. 문제풀이

 

하노이 탑 문제는 대표적인 재귀 문제로 출발 막대, 도착 막대, 나머지 막대로 구분하고 재귀 함수를 구현하면 해결할 수 있다.

1 ~ N번까지의 원판을 출발 막대에서 도착 막대로 옮기는 과정은 1 ~ N-1번 원판을 출발 막대에서 나머지 막대로 이동시키고 N번 원판을 출발 막대에서 도착 막대로 옮긴 후 1 ~ N-1번 원판을 나머지 막대에서 도착 막대로 이동시키면 된다. 이때 1 ~ N-1번 원판을 이동시키는 것 역시 1 ~ N-2번 원판을 옮기는 과정으로 이루어진다. 이를 활용하면 3가지 막대 파라미터를 받는 재귀 함수를 작성할 수 있고 StringBuilder와 BufferedWriter를 활용해서 출력을 해야 시간 제한을 만족할 수 있다.

---

3. 코드

 

import java.io.*;

public class Main {

    private static final StringBuilder sb = new StringBuilder();
    private static int cnt = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        recur(N, 1, 2, 3);

        bw.write(Integer.toString(cnt));
        bw.newLine();
        bw.write(sb.toString());
        bw.flush();
    }

    private static void recur(int N, int from, int mid, int to) {
        if (N == 0) return;

        recur(N - 1, from, to, mid);
        sb.append(from).append(" ").append(to).append("\n");
        cnt++;
        recur(N - 1, mid, from, to);
    }

}

---

4. 후기