문제 링크

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

정답 코드

public class BOJ_11729_하노이탑이동순서_G5 {

    static void hanoi(int n, int from, int to) {
        int mid = 6 - from - to;

        if (n == 1) {
            System.out.println(from + " " + to);
            return;
        }
        if (n >= 2) {
            hanoi(n - 1, from, mid);
            System.out.println(from + " " + to);
            hanoi(n - 1, mid, to);
        }

    }

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

        System.out.println((int)Math.pow(2, N)-1);
        hanoi(N, 1, 3);
    }
}

🧩 전체 실행 순서

👉 CALL hanoi(3, 1 → 3, mid=2)

├─ CALL hanoi(2, 1 → 2, mid=3)
│   ├─ CALL hanoi(1, 1 → 3)
│   │   ├─ MOVE 1 → 3
│   │   └─ RETURN hanoi(1)
│   │
│   ├─ MOVE 1 → 2
│   │
│   ├─ CALL hanoi(1, 3 → 2)
│   │   ├─ MOVE 3 → 2
│   │   └─ RETURN hanoi(1)
│   │
│   └─ RETURN hanoi(2)
│
├─ MOVE 1 → 3
│
├─ CALL hanoi(2, 2 → 3, mid=1)
│   ├─ CALL hanoi(1, 2 → 1)
│   │   ├─ MOVE 2 → 1
│   │   └─ RETURN hanoi(1)
│   │
│   ├─ MOVE 2 → 3
│   │
│   ├─ CALL hanoi(1, 1 → 3)
│   │   ├─ MOVE 1 → 3
│   │   └─ RETURN hanoi(1)
│   │
│   └─ RETURN hanoi(2)
│
└─ RETURN hanoi(3)

---

🔥 요약하면 실행 흐름은 이렇게 진행된다

1. hanoi(3) 은 먼저 hanoi(2, 1→2) 를 호출한다.
2. hanoi(2) 는 다시 hanoi(1) 까지 내려간다 → MOVE 출력
3. hanoi(2) 의 중간 MOVE 실행
4. hanoi(1) 다시 실행 → MOVE
5. hanoi(2) 끝 → RETURN
6. 이제야 hanoi(3) 의 중간 MOVE 실행
7. hanoi(3) 의 오른쪽 hanoi(2) 실행
8. 동일한 방식으로 재귀 진행 → MOVE 출력
9. 모든 재귀 RETURN 후 종료

---

영상 참고

https://www.youtube.com/watch?v=AogMbfRwguk

• 재귀이기 때문에 N이 max 20으로 작은 값이 조건이다.