티스토리 뷰
문제
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
- 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
- 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
아래 그림은 원판이 5개인 경우의 예시이다.
![](https://blog.kakaocdn.net/dn/5OCgJ/btrJWmZI6j9/eBeysUNbzNYup9GRvZec8k/img.png)
입력
첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.
출력
첫째 줄에 옮긴 횟수 K를 출력한다.
두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.
![](https://blog.kakaocdn.net/dn/F93lI/btrJXBVVRpN/RVOENnChyqtgJmBdREXg1k/img.png)
Baekjoon
11729번: 하노이 탑 이동 순서
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로
www.acmicpc.net
예제와 같이 기둥 1, 2, 3이 존재할 때, N개의 원판을 옮긴다면
N-1개의 원판을 현재 경유지인 2번 기둥으로 옮기고, N번째 원판을 최종 목적지인 3번 기둥으로 옮긴다.
N번째 원판이 최종 목적지인 3으로 옮겨졌다면, 나머지 N-1개의 원판을 다시 재배치해야 한다.
N-1개의 원판은 현재 2번 기둥이 시작 기둥이 된다. 그럼 1번 기둥이 경유지가 됨으로 N-2개의 원판을 1번 기둥으로 옮긴다. 그리고 N-1번째 원판을 3번으로 옮긴다. 하노이는 이 과정을 반복하여 최종 목적지로 모든 원판을 옮길 수 있다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Solution11729H {
static StringBuilder answer;
static int count;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
answer = new StringBuilder();
int N = Integer.parseInt(br.readLine());
count = 0;
hanoi(N, 1, 2, 3);
System.out.println(count);
System.out.print(answer);
}
private static void hanoi(int n, int start, int tmp, int end) {
// 마지막 하나는 최종 기둥으로 옮긴다.
if (n == 1) {
answer.append(start + " " + end + "\n");
count ++;
return;
}
// n-1개의 원반을 시작 기둥에서 보조 기둥으로 옮긴다.
hanoi(n - 1, start, end, tmp);
answer.append(start + " " + end + "\n");
count ++;
// 보조 기둥에 있는 원반을 최종 기둥으로 옮긴다.
hanoi(n - 1, tmp, start, end);
}
}
마무리
하노이를 코드로 구현하면서 처음에는 조금 헷갈렸다. 여러 번의 시도 끝에 구현할 수 있었지만, 다음에는 헷갈리지 않게 개념을 확실히 정리하고 해봐야겠다.!
'ALGORITHM > BAEKJOON' 카테고리의 다른 글
[BAEKJOON] 1759. 암호 만들기(JAVA) (0) | 2022.08.22 |
---|---|
[BAEKJOON] 14503. 로봇 청소기(JAVA) (0) | 2022.08.20 |
[BAEKJOON] 2630. 색종이 만들기(JAVA) (0) | 2022.08.17 |
[BAEKJOON] 1992. 쿼드트리(JAVA) (0) | 2022.08.17 |
[BAEKJOON] 1024. 수열의 합(JAVA) (0) | 2022.08.16 |
- Total
- Today
- Yesterday