문제
https://www.acmicpc.net/problem/11729
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
- 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
- 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
아래 그림은 원판이 5개인 경우의 예시이다.
입력
첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.
출력
첫째 줄에 옮긴 횟수 K를 출력한다.
두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.
풀이
접근방법
시간제한 1초, 메모리 256MB이다.
1 ≤ N ≤ 20
재귀를 사용해서 할 수 있는 가장 대표적인 문제이다.
1번 막대에 있는 N개의 원판을 3번 막대로 모두 옮기기 위해서 어떤 과정들이 반복되는 것일까?
1. 원판1을 어딘가로 움직여본다.
2. 원판2를 남은 곳으로 옮긴다.
3. 원판1을 원판2 위로 옮긴다.
4. 원판3을 옮긴다.
...이런 식의 로직을 코드로 구현하려 하면, 상당히 복잡하게 느껴진다.
가장 단순하게, 어쩌면 컴퓨터처럼 생각을 해보자. ( 재귀적 접근 )
1. 막대A의 원판 N개 중 N-1개를 막대B로 옮긴다.
2. 막대A의 원판N을 막대C로 옮긴다.
3. 막대B의 원판 N-1개를 막대C로 옮긴다.조금 더 풀어서 설명하자면,
특정 막대의 원판 N개를 이동시키기 위해서 원판N 위쪽으로 존재하는 N-1개를 모두 이동시켜야 한다.
원판 N-1개를 이동시키기 위해서는 원판N-1 위쪽으로 존재하는 N-2개의 원판을 모두 이동시켜야 한다.
즉 계속 반복되는 것이다. ( 전형적인 재귀 )
simulation(원판의 수, 현재 막대, 목표 막대, 다른 막대) {
if (이동할 막대 == 1) {
원판 이동횟수 증가.
원판 이동 기록 ( 현재 막대의 번호 -> 목표 막대의 번호
return;
}
// 현재 막대에 1개 보다 많은 원판이 존재하는 상태다.
// 전체 N개의 막대 중, N-1개의 막대를 여분의 막대로 모두 옮긴다.
simulation(n - 1, from, other, to);
// 이제 현재 막대에 원판이 1개 남았다.
// 1개의 원판을 최종 목적지로 이동시키자.
simulation(1, from, to, other);
// 위에서 이동시킨 N-1개의 원판을 최종 목적지로 다시 이동시켜 준다.
simulation(n - 1, other, to, from);
}옮긴 횟수를 구하기 위해서는 2개 중 편한 방법을 사용하자.
- 이동시킬 때마다 1씩 증가시키는 방법
- 점화식 2^n-1로 구하는 방법
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
static int N, count;
static StringBuilder sb;
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuilder();
N = stoi(in.readLine());
simulation(N, 1, 3, 2);
System.out.println(count);
System.out.println(sb);
}
private static void simulation(int n, int from, int to, int other) {
if (n == 1) {
count++;
writeMove(from, to);
return;
}
simulation(n - 1, from, other, to);
simulation(1, from, to, other);
simulation(n - 1, other, to, from);
}
private static void writeMove(int from, int to) {
sb.append(from)
.append(" ")
.append(to)
.append("\n");
}
private static int stoi(String s) {
return Integer.parseInt(s);
}
}