Q.11729 자바 : 하노이 탑 이동 순서(S1)

 

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

문제

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

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

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

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

재귀함수 연습을 하다보니

개념은 이해가 됬지만 이를 코드로 작성하려다 보니 머리속에서는 정리가 잘 안되서

적어보면서 생각을 정리해 보려고 한다

 

사실 재귀함수 관련 문제에서 가장 중요한 것은

 

1. 반복되는 패턴을 찾기

2. 이 패턴을 언제까지 반복해야 하는지

(재귀함수 종료 조건)

 

이 두가지를 찾는 것이 가장 중요한 것 같다.

 

그래서 패턴을 발견해 보고 싶어서 혼자 하노이 탑 플레시 게임을

일 하면서 시간이 날 때 3~5층을 반복하면서 2~3시간정도 해봤던 것 같다

엄청난 삽질..

---

 

초반에 할 때 최소 이동 횟수도 맞추지 못했지만, 꾸준히 하다보니 먼저 발견된 패턴이 있다

하노이 탑의 3개의 막대기를 각각 T1, T2, T3이라고 하고

움직여야 하는 고리의 수를 n개라고 하자

예를들어 n = 3일때는 이런 식의 하노이탑이 그려진다

n=3일때의 그림

첫번째로 발견한 패턴은 고리를 옮길 때의 패턴이 있다는 것 이다

1) 옮길 고리가 T1에 있는 경우

    T1의 고리가 홀수개인 경우 T3으로 이동

    T1의 고리가 짝수개인 경우 T2으로 이동

2) 옮길 고리가 T2에 있는 경우

    T2의 고리가 홀수개인 경우 T3으로 이동

    T2의 고리가 짝수개인 경우 T1으로 이동

3) 옮길 고리가 T3에 있는 경우

    T3의 고리가 홀수개인 경우 T2으로 이동

    T3의 고리가 짝수개인 경우 T1으로 이동

 

이런 패턴을 찾았는데,

이후에 옮겨야 할 고리에 대해 패턴을 찾지 못해서

(코드를 어떻게 작성해야 할 지 모르겠어서)

이 방식으로 규칙을 찾는 것은 그만두었다.

---

이후에 좀 더 코드 작성의 관점에서 재귀함수로 어떻게 구현할 수 있을까를 고민하다

n = 3일 경우, 먼저 n=1인 하노이 탑을 T3에 쌓고 n=2인 하노이 탑을 T2에 쌓고, 그 다음 T3에 쌓는다는 점 

n=3일때의 그림

동일한 방식으로 n=4일 경우 먼저 n=1인 탑을 T2에 쌓고,  n=2인 탑을 T3에 쌓고, n=3인 탑을 T2에 쌓은 다음

n=4인 하노이 탑을 T3에 쌓는다는 점을 알게되었다.

한번만 더 작성해보자면

n=5인 경우 n=1인 탑을 T3에, n=2인 탑을 T2에, n=3인  탑을 T3에, n=4인 탑을 T2에, n=5인 탑을 T3에 쌓아야 한다.

 

위 내용에서의 패턴을 작성해보자

간략히 작성하기 위해 n~1번째 원반이 차례대로 쌓여있는 형태를 n탑이라고 작성하겠다.

 

n탑을 T3에 쌓기 위해서는

  1) n-1탑을 T2에 쌓는다

  2) n번째 원반을 T3로 옮긴다

  3) n-1탑을 T3에 쌓는다

  > n탑 완성

  1) n-2탑을 T3에 쌓는다

  2) n-1번째 원반을 T2로 옮긴다

  3) n-2탑을 T2에 쌓는다

  > n-1탑 완성

  ...

  - n이 짝수인경우

   1) 3탑을 T2에 쌓는다

   2) 4번째 원반을 T3로 옮긴다

   3) 3탑을 T3로 옮긴다.

 

   1) 2탑을 T3에 쌓는다

   2) 3번째 원반을 T2로 옮긴다

   3) 2탑을 T2에 쌓는다

 

   1) 1탑(1번째 원반)을 T2에 쌓는다

   2) 2번째 원반을 T3로 옮긴다

   3) 1탑(1번째 원반)을 T3에 쌓는다

 

 -  n이 홀수인 경우

   1) 3탑을 T3에 쌓는다

   2) 4번째 원반을 T2로 옮긴다

   3) 3탑을 T2로 옮긴다.

 

   1) 2탑을 T2에 쌓는다

   2) 3번째 원반을 T3로 옮긴다

   3) 2탑을 T3에 쌓는다

 

   1) 1탑(1번째 원반)을 T3에 쌓는다

   2) 2번째 원반을 T2로 옮긴다

   3) 1탑(1번째 원반)을 T2에 쌓는다

 

처음 입력값 n의 홀수/짝수 여부를 판단하고 결과에 따라 위 패턴을 반복하면 될 것 같다.

코드로 작성하다 보니 어디서(From) 어디로(To) 보내는지에 대한 정의가 필요해 보인다.

위에서 작성한 n의 홀/짝에 따라 옮기는 위치에 대한 패턴이 있는데, 이를 활용해 보려 했지만

삽질을 하다 보니 홀/짝에 따른 접근 방식은 틀린 것 같다

---

코드를 참고하기보단 직접 구현해보고싶어서 하노이탑 이동 횟수에 대해 찾아보니

n층 하노이탑을 옮기기 위해 필요한 이동 횟수는 2^n - 1 이라고 한다

 

n층 하노이탑을 T1에서 T3으로 옮기기 위해

1) n-1층 하노이탑을 T2로 옮기고

2) n번째 고리를 T3에 옮긴 뒤

3) T3에 n-1층 하노이탑을 쌓는다

이 과정에서 n-1층 하노이탑을 두 번 쌓아야 한다.

 

다시 n-1층 하노이탑을 T1에서 T3으로 옮기기 위해

1) n-2층 하노이탑을 T2로 옮기고

2) n-1번째 고리를 T3에 옮긴 뒤

3) T3에 n-2층 하노이탑을 쌓는다

이 과정에서 n-2층 하노이탑을 두 번 쌓아야 하고

 

총 n-1층 하노이탑을 두 번 쌓아야 하므로

n-2층 하노이탑은 총 네 번 쌓아야 한다

 

이 과정을 통해 도출해낸 공식이 2^n - 1 이라고 한다.

원래는 반복문을 이용해서 답을 찾는줄 알고 있었는데,

이 공식을 보니 반복문을 사용하면 안될 것 같다.

마지막으로 생각해 낸 방법은 아래와 같은 형태의 코드이다

private static void hanoiTop(int n){
        if(n == 1){
            return;
        }
        hanoiTop(n-1);
        hanoiTop(n-1);
    }

위에 삽질 과정에서 n개의 고리가 있는 하노이탑을 옮기기 위해서는

 

n-1개의 고리가 있는 하노이탑은 경유지에 한 번, 목적지에 한 번 만들어야 한다는 것을 알았다.

그래서 매개변수로 시작위치, 도착지가 필요해 보이고 경유지 역시 필요해 보인다.

 

세 개의 매개변수를 이용해 n-1개의 고리가 있는 하노이 탑을

경유지에 먼저 쌓고 이후에 목적지에 쌓는 방식을 이용하면 될 것 같다

 

생각한 내용을 바탕으로 코드를 작성했다

private static void hanoiTop(int n, int from, int to, int stay){
        if(n == 1){
            System.out.println(from + " " + to);
            return;
        }
        hanoiTop(n-1, from, stay, to);
        // 출발지(from)에서 목적지(stay)로 이동 경유지(to)를 지나감
        System.out.println(from + " " + to);

        hanoiTop(n-1, stay, to, from);
        /*
        출발지(stay)에서 목적지(to)로 이동 경유지(from)을 지나감
         */
    }

문제 없이 잘 동작하는 것을 확인했다.

 

이후에 시간초과가 나와서 식겁했지만, 

StringBuffer를 이용하니 해결되었다.

전체 코드는 아래와 같다.

 

import java.io.BufferedReader;
        import java.io.IOException;
        import java.io.InputStreamReader;
        import java.util.*;


public class Main {

    private static BufferedReader br;
    private static StringBuffer sb;
    private static int count = 0;
    public static void main(String args[]) throws IOException {

        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuffer();

        int n = Integer.parseInt(br.readLine());
        hanoiTop(n, 1, 3, 2);

        System.out.println(count);
        System.out.println(sb);
    }

    private static void hanoiTop(int n, int from, int to, int stay){
        count++;
        if(n == 1){
            sb.append(from + " " + to + "\n");
            return;
        }
        hanoiTop(n-1, from, stay, to);
        sb.append(from + " " + to + "\n");
        hanoiTop(n-1, stay, to, from);
    }
}