문제
세 개의 장대에 N개의 원판이 있다. 하노이 탑 규칙에 따라 첫 번째 장대에서 세 번째 장대로 모든 원판을 옮기는 이동 횟수와 이동 과정을 출력하라.
입력
첫째 줄에 원판 수 N (1 이상 20 이하)이 주어진다.
출력
첫째 줄에 이동 횟수를, 둘째 줄부터 이동 과정(출발 장대, 도착 장대)을 한 줄씩 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 | 7 1 3 1 2 3 2 1 3 2 1 2 3 1 3 |
풀이
재귀로 하노이 탑의 이동 과정을 출력한다. 이동 횟수는 2^N - 1로 고정이다.
- 이동 횟수 2^N - 1을 비트 시프트 연산으로 계산하여 출력한다
- recur(n, st, ed): n개의 원판을 st에서 ed로 옮기는 재귀 함수
- n-1개를 중간 장대(6-st-ed)로 옮기고, 가장 큰 원판을 ed로 옮기고, n-1개를 ed로 옮긴다
- 기저 조건: n이 0이면 종료
핵심 아이디어: 장대 번호가 1, 2, 3이므로 합이 6이다. 출발(st)과 도착(ed)을 알면 중간 장대는 6-st-ed로 계산할 수 있어 별도 매개변수가 필요 없다.
코드
package com.ssafy.an.day049;
import java.util.Scanner;
public class Day41BOJ11729하노이의탑재귀 { // 11729 하노이의 탑 재귀
static StringBuilder sb;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
sb = new StringBuilder();
int N = sc.nextInt();
sb.append((1 << N) - 1).append("\n");
recur(N, 1, 3);
System.out.println(sb);
sc.close();
}
private static void recur(int n, int st, int ed) {
if (n == 0) return;
recur(n - 1, st, 6 - st - ed);
sb.append(st).append(" ").append(ed).append("\n");
recur(n - 1, 6 - st - ed, ed);
}
}복잡도
- 시간: O(2^N) — 총 2^N - 1번의 이동 출력
- 공간: O(N) — 재귀 스택 깊이