백준 11729번 문제풀이 - 하노이 탑 이동 순서

백준 11729번 문제

 

 

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

11729번: 하노이 탑 이동 순서

 

하노이 탑 이동 순서를 출력하고 총 이동횟수를 출력하는 문제이다.

재귀 알고리즘을 사용하여 메서드를 만들고 결과를 출력하도록 했다.

 

하노이 탑의 이동 알고리즘을 보면 N개의 원판을 이동해야된다고 했을 때

처음엔 중간 기둥으로 N-1개의 원판을 다 옮겨야된다. 그 이후 마지막 원판을 목표 기둥으로 옮긴다.

중간 기둥에 있는 원판을 목표 기둥으로 옮기는 과정을 계속해서 반복하게 된다.

재귀 알고리즘으로 보자면

N-1이 실행되고 처음 기둥에서 목표 기둥으로 끝원판을 옮긴 뒤 N-1이 한번 더 실행되는 구조라고 볼 수 있다.

 

 

 

코딩

 

public class Hanoi {
    public static StringBuilder sb = new StringBuilder();
    // 하노이 탑 이동순서 메서드
    static void move(int N,int x,int y) {
        if (N > 1) {
            move(N-1, x, 6 - x - y); // 1에서 2기둥으로 다 옮김
        }
        sb.append(x+" "+y).append('\n');
        if (N > 1) { // 2에서 3으로 다 옮김
            move(N-1, 6 - x - y, y);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int count = (int)Math.pow(2, N) - 1; // 원판 이동횟수

        System.out.println(count);

        move(N, 1, 3);
        System.out.println(sb);
    }
}

move 메서드를 보면 첫 번째로 N > 1일 때 중간 기둥으로 옮기는 과정에 재귀로 계속 호출되고 N = 1이 되면 첫 번째 기둥에서 목표 기둥으로 원판을 옮긴 뒤 중간 기둥에서 목표 기둥으로 원판을 옮기는 과정이 재귀로 계속 호출되어 실행하게 된다.

 

 

 

 

 

결과

 

StringBuilder를 사용하지 않고 메서드에 매순간 print하도록 했을 때는 시간 초과로 문제가 해결되지 않았지만 StringBuilder를 사용하고 문제를 풀 수 있었다.

 

 

 

 

 

느낀 점

 

재귀 알고리즘 자체는 이해가 됐지만 실제로 적용해보고 코드를 짜는데는 아직 어려움이 많은 것 같다. 재귀 알고리즘을 많이 접해보고 적용시켜보려고 하면서 실력을 키워야될 것 같다.