[백준] 재귀 (11729 : 하노이 탑 이동 순서)

CodingTest/백준

[백준] 재귀 (11729 : 하노이 탑 이동 순서)

브디크리 2023. 9. 12. 23:08

문제

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

11729번: 하노이 탑 이동 순서

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

www.acmicpc.net

해설

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int cnt;
    static StringBuilder sb = new StringBuilder();
    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());
        recur11729(N, 1, 2, 3);
        sb.insert(0, cnt + "\n");
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static void recur11729(int N, int start, int mid, int to){
        if(N==1){
            cnt++;
            sb.append(start).append(" ").append(to).append("\n");
            return;
        }
        //1. N-1개를 A -> B로 이동 (= start(A) 지점의 N-1개의 원판을 mid(B)로 옮긴다.
        recur11729(N-1, start, to, mid);
        
        //1개를 A -> C로 이동 (= start(A) 지점의 N번째 원판을 to 지점으로 옮긴다.)
        cnt++;
        sb.append(start).append(" ").append(to).append("\n");
		
        //N-1 개를 B -> C로 이동 (= mid(B) 지점의 N-1개의 원판을 to 지점으로 옮긴다.)
        recur11729(N-1, mid, start, to);

    }
}

간단하게 알아보기 위해서 아래 그림을 보면

1. 1번의 맨 밑 1개를 옮기기 위해서는 N-1개를 2번으로 옮겨야한다.

2. 다시 2번의 맨 밑 1개를 옮기기 위해서는 N-1개를 1번으로 옮겨야 한다.

3. 마찬가지로 위의 과정을 수행해준다.

이를 통해, 1번과 2번의 가장 아래의 원판을 3번으로 이동시키기 위해서는

1번의 맨 아래의 원판을 이동시키기 위해서는 N-1개의 원판을 2번으로,
반대의 경우에는 1번으로 옮겨야한다는 것을 알았다.

그렇다면, 이제 이를 이용해 해당 코드를 이해해보도록 하자.

private static void recur11729(int N, int start, int mid, int to){
        if(N==1){
            cnt++;
            sb.append(start).append(" ").append(to).append("\n");
            return;
        }
        //1. N-1개를 A -> B로 이동 (= start(A) 지점의 N-1개의 원판을 mid(B)로 옮긴다.
        recur11729(N-1, start, to, mid);
        
        //1개를 A -> C로 이동 (= start(A) 지점의 N번째 원판을 to 지점으로 옮긴다.)
        cnt++;
        sb.append(start).append(" ").append(to).append("\n");
		
        //N-1 개를 B -> C로 이동 (= mid(B) 지점의 N-1개의 원판을 to 지점으로 옮긴다.)
        recur11729(N-1, mid, start, to);

}

3을 예시로 순서도를 그려보면 아래와 같다.