프로그래머스 - 하노이의 탑 java (재귀/반복문) :: 12946

문제 링크

코딩테스트 연습 - 하노이의 탑 | 프로그래머스 스쿨 (programmers.co.kr)

---

문제 이해하기

하노이의 탑 문제는 재귀 함수를 연습하는 대표적인 문제입니다.

재귀 함수를 구현하기 위해서는 규칙을 찾아야 합니다.

n=3일 경우로 예를 들어보겠습니다.

hanoi(n)

이렇게 초기 상태인 [주황+노랑+초록]을 hanoi(n) 이라고 표현하겠습니다.

• 가장 큰 원판을 3번기둥으로 옮기는 방법은?
  가장 아래에 있는 주황색 원판을 3번 기둥으로 옮기기 위해서는 [노랑+초록]이 2번 칸에 있어야 하며, 3번 기둥은 비어있어야 합니다.
  [노랑+초록]원판을 hanoi(n-1)이라고 표현하겠습니다.

• [노랑+초록]을 2번 기둥으로 옮기는 방법
  

  

  
  [노랑+초록]을 2번으로 옮기기 위해서 위의 과정을 거쳐야 합니다.
  1 -> 3 (초록)
  1 -> 2 (노랑)
  3 -> 2 (초록)

즉, [노랑+초록]원판은 1번에서 3번을 임시발판으로 삼아 2번으로 이동했습니다.

이것을 코드로 표현하자면

from: 원래 있던 곳

by: 임시발판

to: 도착해야 할 곳

hanoi(n-1, from ,by, to) = hanoi(2, 1, 3, 2)

• 가장 큰 원판을 3번기둥으로 옮긴 후에는?
  

  

  
  [노랑+초록]원판이 2번기둥에 준비 되었으니, 이제 주황 원판을 3번기둥으로 옮길 수 있게 되었습니다.
  그럼 이제 다시 [노랑+초록] 기둥을 3번기둥으로 옮겨야 합니다.

• [노랑+초록]원판을 3번기둥으로 옮기는 방법
  

  

  
  [노랑+초록]을 3번으로 옮기기 위해서 위의 과정을 거쳐야 합니다.
  2 -> 1 (초록)
  2 -> 3 (노랑)
  1 -> 3 (초록)

즉, [노랑+초록]원판은 2번에서 1번을 임시발판으로 삼아 3번으로 이동했습니다.

이것을 코드로 표현하자면

from: 원래 있던 곳

by: 임시발판

to: 도착해야 할 곳

hanoi(n-1, from ,by, to) = hanoi(2, 2, 1, 3)

• 규칙
  hanoi(n, from, by, to)를 구하기 위해서는 3개의 규칙을 반복되면 됩니다.

1. 내 위에 있는 원판을 모두 옆으로 옮기고 hanoi(n-1, from, to, by)
2. 내가 목적지로 이동하고
3. 옮겨놨던 남은 원판들을 내 위로 가져온다 hanoi(n-1, by, from, to)

• 규칙은 알았는데 출력(이동경로)은 언제해?
  현재 기둥에 원판의 개수가 1개일 때는 바로 옮기면 됩니다 n==1
  또는
  내 위에 있는 원판이 모두 옆으로 옮겨진 후 내가 이동합니다. hanoi(n-1, from, to, by) 이후에 위 규칙과 출력을 표현하면 아래와 같습니다.

• 규칙을 코드로...

  public void hanoi(int n, int from, int by, int to) {        
      if(n==1) {
          출력(from -> to);
      } else {
          hanoi(n-1, from, to, by); // 1->3->2
          출력(from -> to);
          hanoi(n-1, by, from, to); // 2->1->3
      }        
  }

  그러나 우리는 이차원배열에 담아 반환해야 하기 때문에 프로그래머스 정답 기준에 맞춰 코드를 작성해야 합니다.

문제 풀이

1번 풀이

public class Solution {    
    public int[][] solution(int n) {
        int count = (int)Math.pow(2, n) - 1;
        int[][] answer = new int [count][2];

        Hanoi hanoi = new Hanoi(answer);
        hanoi.hanoi(n, 1, 2, 3);

        return hanoi.getHanoiAry();
    }
}

class Hanoi {
    int index = 0;
    int[][] hanoiAry;

    public Hanoi(int[][] hanoiAry) {
        this.hanoiAry = hanoiAry;
    }

    public void hanoi(int n, int from, int by, int to) {        
        if(n==1) {
            hanoiAry[index++] = new int[] { from, to };
        } else {
            hanoi(n-1, from, to, by); // 1->3->2
            hanoiAry[index++] = new int[] { from, to };
            hanoi(n-1, by, from, to); // 2->1->3
        }        
    }

    public int[][] getHanoiAry() {
        return this.hanoiAry;
    }
}

위 설명으로 규칙에 대한 코드 설명을 생략할게요.

배열의 크기를 구하는 것만 주의하면 됩니다.

n(1) = 1

n(2) = 3

n(3) = 7

n(4) = 15

n(5) = 31

딱 봐도 규칙이 보이지 않나요?

hanoi(n)의 이동횟수 = $(2^{n} - 1)$

물론 이거는 눈대중으로도 알 수 있는 규칙이긴 하지만 사실 위의 규칙에서 공식을 도출할 수 있어요.

hanoi(n) 의 이동횟수는 자기자신(1) + hanoi(n-1) 2번 입니다

$ hanoi_{n} = 2 * hanoi_{n-1} + 1 $

우변을 간단하게 만들기 위해 양변에 1을 더하겠습니다.
$ hanoi_{n} + 1 = 2(hanoi_{n-1} + 1)$

이를 순서대로 쭉 나열하면

$hanoi_{n} + 1 = 2(hanoi_{n-1} + 1)$

$hanoi_{n-1} + 1 = 2(hanoi_{n-2} + 1)$

...

$hanoi_{2} + 1 = 2(hanoi_{1} + 1)$

양변을 모두 곱하면

$(hanoi_{n} + 1) (hanoi_{n-1}+1) ... (hanoi_{2}+1) = 2^{n-1}(hanoi_{n-1} +1) (hanoi_{n-2} + 1)(...) (hanoi_{1} + 1)$

각 변의 같은 값을 모두 제거하고, $hanoi_{1} = 1$은 값을 대입하여 계산합니다.

$hanoi_{n} + 1 = 2^{n-1} * 2 = 2^{n}$

$hanoi_{n} = 2^{n} - 1$

테스트 케이스 처리속도

• 🔥 0.29ms ~ 2.99ms

근데 하노이의 탑 재귀방식은 대충 찾아봐도 코드가 엄청 많아요.

제일 효율적이기도 하고, 코드도 간단하기 때문이긴 하지만 괜히 반복문으로 풀어보고 싶더라구요.

2번 풀이

public class Solution12946 {
    public int[][] solution(int n) {
        int count = (int)Math.pow(2, n) - 1;
        int[][] answer = new int [count][2];
        int index = 0;
        Stack<int[]> hanoi = new Stack<>();

        boolean flag = true;
        int from = 1, by = 2, to = 3;
        hanoi.add(new int[] { n, from, by, to });

        while(!hanoi.isEmpty()) {
            int[] pop = hanoi.pop();
            n = pop[0]; from = pop[1]; by = pop[2]; to = pop[3];

            if( n == 1 ) {
                answer[index++] = new int[] { from, to };
                flag = false;
            } else {
                if(flag) {
                    hanoi.add(new int[] { n, from, by, to });
                    hanoi.add(new int[] { n-1, from, to, by });
                }  else {
                    answer[index++] = new int[] { from, to };
                    hanoi.add(new int[] { n-1, by, from, to });
                    flag = true;
                }
            }
        }

        return answer;
    }
}

재귀로 풀지 않을거면 재귀처럼 옮겨야 하는 순서들이 담겨있어야 하거든요.

저는 그걸 Stack으로 해결했어요.

재귀함수에 활용했던 규칙의 순서 그대로 Stack에 담는 방법이에요.

규칙이 3개 있었잖아요?

1번 규칙 수행 이후에 2번 규칙을 수행한 이후에 3번규칙을 수행

이렇게 반복해야 하는데 재귀함수가 아닌 반복문으로는 이거를 그냥 수행할 수가 없어요.

그래서 현재 상태를 나타내기 위해 flag를 사용했어요.

• flag==true : 1번 규칙을 수행하기 전

• flag==false : 1번규칙을 수행한 이후

테스트 처리속도

• 🔥 0.14ms ~ 18.38ms

---