Baekjoon11729*: 하노이 탑 이동 순서

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

 

 

풀이1

1) 규칙성을 찾아야한다
2) 탑의 개수를 항이라고 하고 숫자를 나열해본다

1항: 1 3
2항: 1 2 / 1 3 / 2 3
3항: 1 3 / 1 2 / 3 2 / 1 3 / 2 1 / 2 3 / 1 3

숫자로는 규칙성을 찾을 수 없다. 탑의 개수에 따라 1을 놓는 위치가 다르기 때문이다

3) 실제 탑을 쌓는다고 하고 모형을 그려본다

탑의 개수를 항이라고 정했다. n항에서 마지막 탑은 n번째 탑이다.
각 항마다 n번째 탑을 처음 이동하는 부분만 살펴보면 규칙성을 찾을 수 있다

<1항: 1번 탑을 옮기기 직전의 모습>

1

<2항: 2번 탑을 옮기기 직전의 모습>

2	1

<3항: 3번 탑을 옮기기 직전의 모습>

	1
3	2

<4항: 4번 탑을 옮기기 직전의 모습>

	1
	2
4	3

<5항: 5번 탑을 옮기기 직전의 모습>

	1
	2
	3
5	4
1구역	2구역	3구역

n항에서 n번째 탑을 옮기기 직전: n-1항의 과정을 1구역에서 2구역으로 옮기는 것과 같다
n항에서 n번째 탑을 옮기기: 1구역에서 3구역으로 옮기므로 '1 3' 을 출력하면 된다
n항에서 n번째 탑을 옮긴 직후: n-1항의 과정을 2구역에서 3구역으로 옮기는 것과 같다

4) 코드
n항에서 n번째 탑을 옮기기 직전: n-1번째의 2와 3을 서로 교체해준다
n항에서 n번째 탑을 옮기기:  '1 3' 을 입력한다
n항에서 n번째 탑을 옮긴 직후: n-1번째의 1 → 2로 2 → 1로 교체

2항: 1 2 / 1 3 / 2 3
3항: 2항(2↔3) / 1 3 / 2항(1↔2)
    → 1 3 / 1 2 / 3 2 / 1 3 / 2 1 / 2 3 / 1 3

규칙을 알았으므로 탑 이동거리의 최솟값을 미리 알 수 있다
n번째 탑을 옮기기 직전까지 경우의 수: n개
n번째 탑을 옮기는 경우의 수: 1개
n번째 탑을 옮긴 후 경우의 수: n개
탑 최소 이동 개수: 2n+1개

이를 통해 배열을 미리 생성할 수 있게된다

5) 주의점
i) n항을 만들고 n+1항을 만든다고 가정한다
n+1항의 앞부분은 n항이 이미 있기 때문에 그대로 냅두고  2와 3을 교체하면된다
뒷부분은 복사되어있지 않기 때문에 먼저 뒷부분을 복사한 후 앞부분의 값을 고쳐준다ii) n의 증감은 N과 같아야한다. n = 2*n + 1로 증가한다

import java.io.*;
public class Main {
public static void main(String[] args) throws IOException{
	 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	 StringBuilder st = new StringBuilder();
	 int[] min = new int[21];
	 min[1] = 1;
	 //최소 경로를 미리 알 수 있다. 그 값을 저장한 배열을 만든다. 계산을 위해 +1
	 for(int i = 1; i<20; i++) {
		 min[i+1] = min[i]*2+1;
	 }
	 int N = Integer.parseInt(br.readLine());
	 int sum = min[N];
	 int[][] hanoi = new int[2][sum];

	 hanoi[0][0] = 1;
	 hanoi[1][0] = 3;
	 moveTower(N, hanoi, sum);
	 
	 for(int i =0; i<min[N]; i++) {
		 st.append(hanoi[0][i]).append(" ").append(hanoi[1][i]).append("\n");
	 }
     System.out.println(sum);
	 System.out.println(st.toString());
}
public static void moveTower(int N, int[][] hanoi, int sum) {
	int n = 1;
//1부터 시작해서 loop가 반복될 때 마다 n은 증가한다
//N보다 커지면 멈춘다
	while(n != sum) {
		  for(int i = 0; i<n; i++) {
					hanoi[0][n+1+i] = hanoi[0][i];
					hanoi[1][n+1+i] = hanoi[1][i];
//뒤쪽부터 값을 복사한 후 처리한다
//0~n까지 값 -> n+1~2n으로 복사 
				
		  for(int j =0; j<2; j++) {
				switch(hanoi[j][i]) {
				case 1: hanoi[j][n+i+1] = 2; break;
				case 2: hanoi[j][n+i+1] = 1; break;
//복사한 값의 1 -> 2, 2->1 로 변환
				}
			}
		  }
		for(int i = 0; i<n; i++) {
			for(int j =0; j<2; j++) {
				switch(hanoi[j][i]) {
				case 2: hanoi[j][i] = 3; break;
				case 3: hanoi[j][i] = 2; break;
				}
			}
		}
		hanoi[0][n] = 1;
		hanoi[1][n] = 3;
//n번째 탑이 1 3 으로 이동하는 것은 고정이다
		n = 2*n +1;
//n ++가 아님을 유의한다, n은 N 수열의 증감과 같이 증가한다
	}
}
}

 

풀이2

위의 원리를 파악하고 재귀의 작동방식을 사용하면 코드의 길이가 매우 짧아진다.

출력 단계를 3가지로 분류한 다음(출발, 경유, 도착) 바로바로 값을 치환하는 방식으로 답을 구성한다

import java.io.*;
public class Main {
	public static StringBuilder sb = new StringBuilder();
	
	static void Hanoi(int N, int x, int y, int z) { //탑의 수:N x출발 y경유 z도착
		if(N==1) {
			sb.append(x+" "+z+"\n");
			return;
//하노이 메소드 자기 자신을 호출한다
		}
		Hanoi(N-1, x, z, y);
//현재 n의 앞부분은 이전 n-1항이 1구역에서 2구역으로 이동한 메소드이다
		sb.append(x+" "+z+"\n");
		Hanoi(N-1, y, x, z);
//현재 n은 이전 n-1항이 2구역에서 3구역으로 이동한 메소드이다
	}
	static int min(int x) {
		if(x==1) {
			return 1;
		}
		return 2*min(x-1)+1;
//최소값 메소드는 자기 자신의 이전 메소드의 2배+1이다
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		System.out.println(min(N));
		Hanoi(N, 1, 2, 3);
		System.out.println(sb);
	}
}