문제 출처

단계별로 풀어보기 > 재귀 > 하노이 탑 이동 순서
https://www.acmicpc.net/problem/11729

문제 설명

하노이 탑 규칙에 따라서 원판의 개수 N이 주어질 때
출력 첫째 줄에는 이동 횟수, 둘째줄부터는 이동 과정을 출력하라

접근 방법

이동 횟수의 경우 점화식 아래 그림과 같은 과정으로 나온다.

즉, 원판 N개의 이동 횟수는 2^N -1임을 알 수 있다.

또한, 하노이 탑의 원판 이동 과정은

가장 큰 원판은 막대 A에서 C로 이동하기 위해선 n-1 개의 원판이 이동해야하고,
이 후 A에서 가장 큰 원판이 C로 이동,
마지막으로 B에 있는 n-1 개의 원판이 C로 이동한다.

해당 과정을 재귀를 이용하여 가장 큰 원판을 이동 시키는 것을 시작으로 재귀를 통해 가장 작은 원판을 이동시키는 것으로 반복한다.

import java.io.*;

public class 하노이_탑_이동_순서 {

    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

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

        bw.write(String.valueOf((int)(Math.pow(2,N) - 1)));
        bw.write("\n");

        Hanoi(N,1,2,3);

        bw.flush();
        bw.close();


    }

    public static void Hanoi(int N, int start, int mid, int to) throws IOException{

        if(N==1){
            bw.write(start + " " + to + "\n");
            return;
        }

        Hanoi(N-1,start, to, mid);

        bw.write(start + " " + to  + "\n");

        Hanoi(N-1, mid, start, to);
    }
}

Review

import java.io.*;

public class 하노이_탑_이동_순서_review {

    public static BufferedWriter bw;

    public static void Hanoi(int N, int start, int mid, int to) throws IOException {

        if(N == 1){
            bw.write(start + " " + to + "\n");
            return;
        }


        Hanoi(N-1,start,to,mid);

        bw.write(start + " " + to + "\n");

        Hanoi(N-1,mid,start,to);


    }

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

        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int moveCount = (int) (Math.pow(2,N)-1);
        bw.write(String.valueOf(moveCount));
        bw.write("\n");

        Hanoi(N,1,2,3);

        bw.flush();
        bw.close();
        br.close();


    }

}

알게된 점

처음 문제를 접했을 땐, 막대 3개를 stack형태로 구현해보려고 했으나, 과정이 어려워서 다른 사람의 풀이를 참조했다.

출처
https://st-lab.tistory.com/96
Review

        Hanoi(N-1,start,to,mid);

        bw.write(start + " " + to + "\n");

        Hanoi(N-1,mid,start,to);

해당 코드에서 java bw.write(start + " " + to + "\n");는 현재 단계에서 가장 마지막 원판을 옮기는 경우를 출력한다.

문제푼 흔적

Review