백준 11729번: 하노이 탑 이동 순서
문제풀이 핵심
왼쪽부터 오른쪽 방향으로 1,2,3번 탑 / 작은 원판부터 큰 원판 순서대로 1,2,...,N번 원판이라고 했을 때,
-
N개의 원판을 옮기는 방법은?
1. N-1개의 원판을 2번 탑에 쌓기
2. N번 원판 3번 탑에 쌓기
3. N-1개의 원판 3번 탑에 쌓기 -
N개의 원판을 옮기기 위해 N-1개의 원판이 어떻게 옮겨지는지 알아야 한다 -> 재귀를 떠올린다.
- N = 7일 때, N = 6 호출
- N = 6일 때, N = 5 호출
- ...
- N = 1일 때, 이동
즉, N-1개의 원판을 2번 탑에 쌓아놔야 된다.
N-1개의 원판을 2번 탑에 쌓아놓는 방법은 N-1개의 원판을 3번 탑에 쌓아놓는 방법과 과정이 같다. 이동하는 탑만 다를 뿐.
즉, 같은 로직에서 시작 탑 / 목표 탑이 어딘지만 바꿔주면 된다.
시작 탑 : 이동 전에 위치하고 있는 탑
목표 탑 : 이동 후에 위치하게 될 탑
예를 들어, N=3일 때, 2개의 원판을 2번 탑에 쌓아놔야 한다.
N=2일 때의 답을 구하면 2개의 원판을 3번 탑에 쌓고 끝이겠지만, 현재 N=3일 때의 답을 구하기 위한 것이므로 이를 2번 탑에 쌓는 것으로 목표 탑을 바꾸는 것이다.
그 후에, 3번 원판을 3번 탑에 옮긴 뒤, 다시 2번 탑에 있는 2개의 원판을 3번 탑으로 옮긴다. 2개의 원판을 2번 -> 3번으로 옮기는 것 역시 같은 로직이고 원래 있던 탑, 목표 탑만 바뀌는 것이다.
이를 코드로 옮겨보자.
hanoi(int N, int start, int mid, int to) 함수가 원판을 옮기며 이동 결과를 출력하는 함수라고 했을 때, 내용은 다음과 같다.
N : 옮기려고 하는 원판의 총 개수
start : 시작 탑 - N개의 원판이 처음에 위치하고 있는 탑
mid : 중간 탑 - 시작/중간 탑을 제외하고 남는 탑이라고 생각하면 된다.
to : 목표 탑 - 최종적으로 N개의 원판을 위치시킬 탑
N = 1일 때, 원판이 하나뿐이므로 바로 start에서 to로 이동시키며 이동결과를 출력한다.
N != 1일 때,
- N-1개의 원판을
mid로 옮긴다. - N번 원판을
to로 옮긴다. mid에 있던 N-1개의 원판을to로 옮긴다.
이를 코드로 보면,
hanoi(N-1, start, to, mid): N-1개의 원판을 시작 탑에서 중간 탑으로 옮겨 놓는다.System.out.println(start + " " + to): N-1개의 원판을 옮기고 남은 가장 큰 N번 원판을 시작 탑에서 목표 탑으로 옮긴다.hanoi(N-1, mid, start, to): 중간 탑으로 옮겨 놓았던 N-1개의 탑을 목표 탑에 쌓는다.
참고 : N개의 원판을 옮기는 최소 이동 수는 2^N - 1 이다.
Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int n;
static StringBuilder sb;
public static void hanoi(int N, int start, int mid, int to) {
if (N == 1) {
sb.append(start).append(' ').append(to).append('\n');
return;
}
hanoi(N - 1, start, to, mid);
sb.append(start).append(' ').append(to).append('\n');
hanoi(N - 1, mid, start, to);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuilder();
n = Integer.parseInt(br.readLine());
sb.append((int) Math.pow(2, n) - 1).append('\n');
hanoi(n, 1, 2, 3);
System.out.println(sb);
}
}
References
https://st-lab.tistory.com/96 결국엔 해당 블로그 코드를 보고나서야 문제를 해결했다..
하노이 탑 게임 문제 규칙을 찾아내겠다고 시작햇다가 재밌어서 1시간 가까이 했다..
