[백준/BOJ] 11729번 하노이 탑 이동 순서 (자바/Java)
https://www.acmicpc.net/problem/11729
11729번: 하노이 탑 이동 순서
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로
www.acmicpc.net
1. 문제
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
- 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
- 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
아래 그림은 원판이 5개인 경우의 예시이다.
입력
첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.
출력
첫째 줄에 옮긴 횟수 K를 출력한다.
두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.
예제 입력 1
3예제 출력 1
7
1 3
1 2
3 2
1 3
2 1
2 3
1 32. 풀이
이 문제는 알고리즘 중 재귀(Recursion)에 관한 문제입니다.
재귀의 가장 대표적인 문제로써, 하노이 탑에 대한 규칙을 잘 모르시거나 직접 해보시길 원하시는 분은 아래의 링크를 들어가셔서 플레이 해보실 수 있습니다.
https://www.mathsisfun.com/games/towerofhanoi.html
그렇다면 이 문제는 어떻게 재귀를 이용하여 풀어야할까요??
생각보다 단순합니다.
만약 우리가 n개의 탑을 옮겨야한다고 생각해봅시다. 그러면 우리는 이 n개의 탑을 옮기기 위해서 어떻게 해야할까요??
재귀적으로 한번 생각해봅시다. 맨 밑의 n개만 빼고 n-1개의 탑을 두번째에 옮긴 후, 하나만 남은 n개를 세번째에 옮긴 후에 나머지 n-1개의 탑을 세번째에 옮기면 됩니다.
그림으로 다시 확인해보겠습니다.
이렇게 되면 문제가 제시하는 조건을 만족하게 됩니다!!
그럼 여기서 저희는 'n-1개의 탑을 어떻게 두번째로 옮길까?'가 관건입니다. 사실 이 또한 재귀를 이용하여 n-2개의 탑을 세번째에 옮기고 n-1을 두번째에 넣고 세번째에 있는 n-2개를 두번째로 옮기면 되겠죠??
이것이 재귀를 푸는 방법이자 노하우라고 생각합니다.
따라서 우리는 다음과 같은 방법을 이용해서 재귀 함수를 구현하고자 합니다. 이 문제에서는 하노이탑을 옮기는데 필요한 횟수 또한 구하라고 하였으므로, 재귀 함수를 호출하여 다른 재귀 함수를 호출하기 전 cnt를 늘려주면서 카운트하는 방식으로 진행하겠습니다.
또한 하노이 탑에서는 3군데에 탑을 배치할 수 있습니다. 우리가 재귀 함수의 인자로
(int a, int b, int n) -> a에서 b로 n개를 옮기기
를 전달해준다고 하면 a와 b를 제외한 나머지를 6-a-b로 구할 수 있다는 것을 알고있으면 됩니다!!
(여기서 a, b, 6-a-b는 1, 2, 3 중 하나겠죠??)
이제 코드를 구현해봅시다.
import java.util.Scanner;
public class Main {
static StringBuilder sb = new StringBuilder();
static int cnt = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
move(1, 3, n); // 1에서 3으로 n개를 옮겨라!
System.out.println(cnt);
System.out.println(sb);
}
public static void move(int a, int b, int n){
if(n==1){
cnt++;
sb.append(a+" "+b+"\n");
return;
}
move(a, 6-a-b, n-1); // a에서 c로 n-1개를 옮겨라!!
cnt++;
sb.append(a+" "+b+"\n"); // 그 다음 a에서 b로 n번째를 옮긴다.
move(6-a-b, b, n-1); // 그 후, c에서 b로 n-1개를 옮겨라.
}
}
3. 결과
4. 총평
- 우리가 평소 가지고있던 절차 지향적 사고에서 재귀적 사고로 바꿔볼 필요가 있습니다. 꾸준한 노력을 통해 재귀적 사고를 하는 법을 익혀야할 것 같습니다.