[JAVA/백준] 11729 하노이 탑 이동 순서

• 하노이 탑 이동 순서 문제 링크

• 제한사항

  시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
  1 초	256 MB	26629	12861	9988	48.275%

문제

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

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

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

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

입력

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

출력

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

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

문제 접근

하노이 탑은 전형적인 재귀함수 를 이용해 해결하는 문제이다. 문제를 풀다가 재귀에 대해 아직도 잘 모르고 있다는 생각이 들었다. 그래서 이 문제를 바탕으로 재귀에 대해 한번 정리하고 가려고 한다.

재귀

• 재귀란?

  • 재귀(recursion)라는 단어의 정의는 다음과 같다.

    재귀(再歸) : 원래의 곳으로 다시 돌아오는 것

    recursion : 반복, 되풀이

  • 즉, 어떠한 하나의 행위가 계속 반복되는 것이다.

• 알고리즘에서 재귀란?

  • 어떤 문제를 해결하기 위해 해당 문제의 조금 더 작은 케이스를 대입해 문제를 최대한 간단하게 만들어 해결하는 것이다.
  • 재귀는 문제가 간단해질 때까지 입력된 케이스를 축소하는 것을 반복하는 것이다.

• 재귀함수?

  • 재귀함수는 재귀 방식으로 함수를 호출해 문제를 해결하는 방법이다.

    함수: 하나의 입력 값에서 하나의 결과값이 도출되고, 그 결과는 예측 가능해야한다.

    참고문서

  • 호출된 함수들은 스택(Stack) 메모리에 쌓이기 때문에, 함수가 끝없이 호출되다 스택오버플로우 발생 할 수 있어서 꼭 함수 종료 조건을 작성해서 함수의 종료점을 만들어야 한다

    • 기저 사례(base case) 라고 한다

재귀를 어떻게 적용?

• 문제 요구사항

  • 원판의 개수 N (1 ≤ N ≤ 20)개를 1번 장대에서 3번 장대까지 최소한의 동작 옮기는 것이다.
  • 입력값으로 정수형 N (1 ≤ N ≤ 20)이 정해지면
  • 출력은 각 N개의 원반의 이동 횟수와 순서를 뽑는 것이다.

• 하노이(N)이라는 함수가 있다고 치자,

  • 하노이(2) 일때의 결과값은 아래와 같다.

    3
    1 2
    1 3
    2 3

    • 하노이(2) 함수의 실행과정을 그림으로 나타내보았다.

      

    • 2개의 원반을 3번 장대까지 옮기려면 가장 큰 원반인 원반2가 장대3의 가장 밑으로 가야한다.

    • 원반2가 움직이기 위해서는 위에 쌓인게 없어야 한다 -> 원반1이 이동해야한다.

    • 원반2는 장대3으로 가야하므로, 원반1은 장대1에서 장대2로 가야한다.

    • 위에 아무 것도 없어진 원반2는 장대1에서 장대3으로 이동할 수 있다.

    • 이제 원반1을 장대2에서 장대3으로 옮기면 문제를 해결할 수 있다.

    • 요약하면,

      1. 마지막 원반을 제외한 나머지를 장대2로 보내고
      2. 마지막 원반을 장대3으로 보낸다
      3. 장대2에 있는 원반을 장대3으로 보낸다

• 하노이(3) 일때의 결과값은 아래와 같다.

  7
  1 3
  1 2
  3 2
  1 3
  2 1
  2 3
  1 3

  
  • 원반3을 장대3으로 이동하기 위해서 원반1,원반2를 장대2로 이동시켜야한다.
  • 원반1,원반2가 장대2로 가려면! 장대2에 원반2가 바닥에 있어야하고 원반2가 장대2로 이동하기 위해서는 원반1이 다른 곳(장대3)으로 이동한 상태여야한다. => 앞에 정의한 하노이(2)와 이동 방식이 똑같다!
  • 4번째 이동에서 장대1에 있던 원반3이 이동했다
  • 이제 장대2번에 있는 두개의 원반을 장대3으로 옮기면 문제가 해결된다 => 이 부분도 하노이(2)와 같은 형태라고 볼 수 있다!

• 하노이(3)을 옮길 때는 하노이(2)가 두번 호출 되는 것을 보면, 하노이(N)은 두번의 하노이(N-1) 재귀과정으로 해결 할 수 있다고 유추할 수 있다.

• 같은 형태의 함수에 입력값을 작게해서 문제를 해결할 때까지 호출 하는 것 => 재귀함수를 이용해서 하노이 탑 문제를 풀 수 있다.

문제해결 과정 구체화

• 가정 : 하노이(N)은 하노이(N-1)의 재귀 두 번과 한번의 N의 이동(장대1->장대3)을 통해 해결할 수있다

  1. 원반N을 제외한 원반1~원반N-1을 장대1 -> 장대2로 이동 [첫번째 재귀]
  2. 원반N을 장대1 -> 장대3으로 이동 [첫번째 재귀가 끝나면 출력]
  3. 장대2에 있는 N-1개의 원반(원반1~원반N-1)을 장대3으로 이동[두번째 재귀]

• 기저사례(base case)

  • 하노이(1)인 경우 원반1 위에 방해되는 원반이 없기 때문에 원반1은 바로 장대1에서 장대3으로 이동 시킬 수 있다. => 재귀를 돌 필요가 없다.

    

  • 즉, 하노이(N) 함수의 종료시점(가장 작은 케이스)는 1이 된다.

• 장대1을 start, 장대3을 end, 장대2 via로 정의했을 때,

• 하노이(N)을 구체적으로 hanoi(N, start, end, via) 정의할 수 있다.

• 첫번째 재귀인 하노이(N-1)는 중간통로로 원반들을 보내는 것으로, hanoi(N-1, start, via, end) 로 정의할 수 있다.

• 첫번째 재귀가 끝나면 hanoi(N, start, end, via)의 내용을 출력한다.

• 장대2에 있는 원반들을 장대3으로 보내는 두번째 재귀는, hanoi(N-1,via,end,start)로 정의할 수 있다.

• N==1이면, hanoi(1, start, end, via)의 내용을 출력하고 재귀를 끝낸다.

주의할점

• 시간제한이 1초이고 하노이의탑은 2^n번 연산이 걸린다.

• 출력을 할 때, System.out.print를 사용하게 되면 시간초과에 걸린다. 버퍼를 사용하자.

소스

import java.io.*;

public class Main {
    static BufferedWriter bw;
    public void print(int start, int end) {
        try {
            bw.write(start+" "+end+"\n");
        } catch (Exception e) {
            e.printStackTrace();
        }

    }
    public void hanoi(int n, int start, int end, int via) {
        if(n==1){
      print(start, end);
      return;
    }    
        hanoi(n-1, start, via, end);
        print(start, end);
        hanoi(n-1, via, end, start);

    }
    public static void main(String[] args)  {

        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int N = Integer.parseInt(br.readLine());
            bw.write((int)(Math.pow(2, N)-1)+"\n");

            new Main().hanoi(N, 1, 3, 2);
            br.close();
            bw.flush();
            bw.close();
        } catch (Exception e) {
            e.printStackTrace();
        }

    }
}