하노이의 탑

N개의 원판은 총 2N -1 번의 과정을 거쳐 이동할 수 있습니다. 하지만 어떠한 과정으로 원판을 옮겨야 2N -1 번만에 옮길 수 있는지는 아직 모릅니다. 원판이 N개 있을 때, Hanoi 함수에서 어떠한 과정으로 2N -1 번만에 옮길 수 있는지 과정을 리턴하세요.

리턴값의 표기 방법은 다음과 같습니다.

• 3개의 기둥은 순서대로 각각 1, 2, 3번으로 표기합니다.
• 원판을 기둥1에서 기둥3으로 이동했다면 [1, 3]으로 표기합니다.
• 원판을 기둥3에서 기둥1로 이동했다면 [3, 1]로 표기합니다.

이러한 이동 순서를 담는 배열을 리턴하면 됩니다. 예를들어 N이 2라면 아래 그림과 같이 옮길 수 있으므로

리턴값은 [ [1,2], [1,3], [2,3] ]입니다.

기본적인 하노이탑 문제인데, 재귀를 사용한다는건 알았지만 짜면서 결정적인 로직의 흐름이 이어지지 않아 풀기 힘들었다.

또 좌표값을 저장함에 있어서 리스트를 2차원 배열로 바꾸는 방법이 잘 생각이 나지 않아서 고민을 했고, 결국 하나씩 다 넣어준 다음 나머지 연산으로 배열에 복사하는 방법을 사용했다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
class Hanoi {
 
    public void move(List<Integer> list, int from, int to) {
        list.add(from);
        list.add(to);
    }
 
    public void hanoing(List<Integer> list, int n, int from, int by, int to) {
        if (n == 1) {
            move(list, from, to);
        } else {
            hanoing(list, n - 1, from, to, by);
            move(list, from, to);
            hanoing(list, n - 1, by, from, to);
        }
    }
 
    public int[][] hanoi(int n) {
        // 2차원 배열을 완성해 주세요.
        int[][] answer = null;
        List<Integer> list = new ArrayList<>();
        int num = (int) (Math.pow(2, n) -1);
        answer = new int[num][2];
        
        hanoing(list, n, 1, 2, 3);
        
        for(int i = 0; i < list.size();i++) {
            if(i%2 == 0) {
                answer[i/2][0] = list.get(i);
            } else {
                answer[i/2][1] = list.get(i);
            }
            
        }
        return answer;
 
    }
 
    // 아래는 테스트로 출력해 보기 위한 코드입니다.
    public static void main(String[] args) {
        Hanoi h = new Hanoi();
        System.out.println(Arrays.toString(h.hanoi(2)));
    }
}