Baekjoon11729*: 하노이 탑 이동 순서

Baekjoon11729*: 하노이 탑 이동 순서

문제

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

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

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

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

입력

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

출력

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

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

추상화

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

"); } 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+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

모범 답안 탐색

늘 문제를 풀고 코드리뷰를 하는데 역시 갈 길은 멀다

위 출력 단계를 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+"

"); return; //하노이 메소드 자기 자신을 호출한다 } Hanoi(N-1, x, z, y); //현재 n의 앞부분은 이전 n-1항이 1구역에서 2구역으로 이동한 메소드이다 sb.append(x+" "+z+"

"); 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); } }

from http://devyoseph.tistory.com/74 by ccl(A) rewrite - 2021-10-16 03:02:07