Menu

Subscribe

[JAVA/백준] 재귀: 하노이 탑 이동 순서

HEESOO on Boj

👀 문제

https://www.acmicpc.net/problem/11729

👊 도전

1. 설계

  1. 원반 n개를 이동하는 문제는 원반 n-1개로 이동하는 문제로 세분화되고, 결국 원반 1개를 이동하는 것과 같게 된다.
  2. 하노이 탑을 해결하기 위해서 1번 타워에서 3번 타워로 옮기는 순서는, 1->3->2로 옮긴 후, 2->1->3순으로 옮기면 된다.

2. 구현 (성공 코드)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import java.util.Scanner;

/**
 * 
 * @author HEESOO
 *
 */
public class Main {
	static int cnt=0;
	static StringBuilder sb=new StringBuilder();
	public static void hanoi(int num, int from, int by, int to){
		cnt++;
		if(num==1)
			sb.append(from+" "+to+"\n");
		else{
			hanoi(num-1, from, to, by);
			sb.append(from+" "+to+"\n");
			hanoi(num-1, by, from, to);
		}
	}
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int n=input.nextInt();
		hanoi(n,1,2,3);
		System.out.println(cnt);
		System.out.println(sb);
	}
	
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. 재귀를 이용하여 하노이 탑을 옮긴다.
    • 원판이 하나일 때에는 해당 원판을 원하는 곳으로 옮긴다.
  2. StringBuilder를 이용하여 출력한다.
    • 최종 옮긴 횟수를 출력한 후, 순서를 출력해야하는데 최종 횟수는 하노이 재귀가 모두 끝난 후에 값이 완성되므로 StringBuilder를 이용하지 않으면 출력 순서를 맞출 수 없다.
    • 따라서 StringBuilder를 이용하여 이동 순서를 따로 저장해둔 후 cnt를 출력한 후 StringBuilder값을 출력한다.

👏 해결 완료!

하노이 개념은 알고 있었지만 코드화하는 것이 어려웠다. 아직도 완벽히 이해하지는 못했다.

참고