[📝 백준] 실버1 / 11729 / 하노이 탑 이동 순서

🔗 문제 링크 : https://www.acmicpc.net/problem/11729

 

이 문제를 풀면서 재귀에 대한 감이 왔다. 재귀의 작동 순서는 n개 라는 목표가 있다면 n-1, n-2, ... , 1 까지 찍고 다시 하나 하나 바로 올라오는 과정에서 문제가 해결된다. 이번 하노이 탑 문제에서도 이러한 재귀의 규칙이 적용된다. 총 3개의 스톤을 옮겨야한다면, 2개짜리 먼저 해결, 1개짜리 먼저 해결 다 해결하면 다시 하나씩 올라와..! 이런 느낌이다. 이 문제는 스스로 생각해내기에는 한계가 있어서 다른 해설을 보면서 공부했다.

 

🔗 참고 링크 : https://st-lab.tistory.com/m/96

- 아래 코드는 위 참고 링크로 부터 가지고 온 정답 코드이다. 먼저 아래 코드를 잘 이해하고, 나만의 방식대로 다시 한번 작성해보려고 한다.

public class Baek11729 {

    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int N = in.nextInt();

        sb.append((int) (Math.pow(2, N) - 1)).append('\n');

        Hanoi(N, 1, 2, 3);
        System.out.println(sb);

    }

	/*
		N : 원판의 개수
		start : 출발지
		mid : 옮기기 위해 이동해야 장소
		to : 목적지
	 */

    public static void Hanoi(int N, int start, int mid, int to) {
        // 이동할 원반의 수가 1개라면?
        if (N == 1) {
            sb.append(start + " " + to + "\n");
            return;
        }

        // A -> C로 옮긴다고 가정할 떄,
        // STEP 1 : N-1개를 A에서 B로 이동 (= start 지점의 N-1개의 원판을 mid 지점으로 옮긴다.)
        Hanoi(N - 1, start, to, mid);

        // STEP 2 : 1개를 A에서 C로 이동 (= start 지점의 N번째 원판을 to지점으로 옮긴다.)
        sb.append(start + " " + to + "\n");

        // STEP 3 : N-1개를 B에서 C로 이동 (= mid 지점의 N-1개의 원판을 to 지점으로 옮긴다.)
        Hanoi(N - 1, mid, start, to);

    }
}

예제에 나와있는 것 처럼 N = 3 인 경우로 직접 과정을 확인해보도록 하자.

Hanoi(3, 1, 2, 3) // 3번째 원판이 3번으로 가야함 -> 그전에 2번째 원판부터! (N-1 번째 원판들이 2번으로 가야함)

Hanoi(2, 1, 3, 2) // 2번째 원판이 2번으로 가야함 -> 그전에 1번째 원판부터! (N-1 번째 원판들이 3번으로 가야함)

Hanoi(1, 1, 2, 3) // (출력) 1 3 -> N-1 부터 1 원판까지 이동, N번째 원판이 2번으로 갈차례

// (출력) 1 2 -> N-1 부터 2번으로 다시 올라감

Hanoi(1, 3, 1, 2) // (출력) 3 2 -> N-1 부터 1 원판까지 이동, N번째 원판이 3번으로 갈차례

// (출력) 1 3 -> N-1 부터 3번으로 다시 올라감

Hanoi(2, 2, 1, 3) // 2번째 원판이 3번으로 가야함 -> 그전에 1번째 원판부터!

Hanoi(1, 2, 3, 1) // (출력) 2 1

// (출력) 2 3

Hanoi (1, 1, 2, 3) // (출력) 1 3

# 출력값 정리
1 3
1 2
3 2
1 3
2 1
2 3
1 3

N-1 번째 원판들이 나머지 한 쪽으로 이동 후 원래 자리에 N 번째 원판이 이동하는 것은 이해, 그런데 나머지 N-1 개의 원판들이 제자리를 찾아가는 과정은 완전히 이해하지 못한 것 같다. 참고 글을 보고 나니, 어처피 마지만 가장 큰 원판이 그 자리에 있는 것은 의미가 없기 때문에 단순이 현재 위치에서 다른 위치로 옮겨가는 상황에서의 재귀 호출이라고 보아도 될 것 같다. 아직 정리가 더 필요할 듯 하다...