백준 11729 풀이

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

하노이탑 문제

오랜만에 보는 하노이탑 문제라 잘 기억이 안나 구글에 검색해 기본적인 원리를 보고 코드를 작성했다. ㅠㅠ

하노이탑의 핵심은 n개의 원판이 있을 때, n번째 원판이 가장 끝 자리로 가기 위해서는 n-1개의 원판이 중간 자리에 있어야 한다.

저 원리를 알았다면 금방 코드를 작성해 문제를 해결할 수 있는 간단한 문제였다.

n==1일 경우, 간단하게 가장 끝 자리로 옮기고 끝이다.

그 외에는 재귀적 호출을 통해 풀어 낼 수 있다.

import java.io.*;
import java.util.Stack;

public class Main {
    static Stack<Pair> stack;
    static int count = 0;

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String num = br.readLine();
        int n = Integer.parseInt(num);
        stack = new Stack<>();
        hanoi(n, 1, 2, 3);

        bw.write(Integer.toString(stack.size())+"\n");
        for (Pair p : stack) {
            String line = p.first + " " + p.second + "\n";
            bw.write(line);
        }

        bw.close();
        br.close();
    }

    public static void hanoi(int n, int a, int b, int c) {
        if (n == 1) {
            Pair p = new Pair(a, c);
            stack.push(p);
        } else {
            // n-1개의 원판을 b로 이동
            hanoi(n - 1, a, c, b);
            Pair p = new Pair(a, c);
            stack.push(p);
            // n-1개의 원판을 b에서 c로 이동
            hanoi(n - 1, b, a, c);
        }
    }
}

class Pair implements Comparable<Pair> {
    public int first;
    public int second;

    public Pair() {
    }

    public Pair(int a, int b) {
        this.first = a;
        this.second = b;
    }

    @Override
    public int compareTo(Pair o) {
        if (this.second < o.second)
            return -1;
        else if (this.second == o.second) {
            if (this.first < o.first) {
                return -1;
            } else
                return 1;
        } else
            return 1;
    }
}

이 문제에서는 재귀 호출에 더해 스택을 이용했는데 재귀호출 방식과 스택 방식은 동일하기 때문에 이동경로를 저장하기 쉽고 문제에서 이동이 완료된 후 이동횟수를 먼저 출력해야 하기때문에 스택을 이용하면 이동횟수를 먼저 출력하기 용이하기 때문이다.