[12946] 하노이의 탑

✔ 하노이의 탑

[프로그래머스 12946]

문제 분석하기

1번 기둥의 가장 큰 원판은 3번 기둥으로 갈 수 있도록 나머지 원판을 옮기는 것을 반복

 

예1) n = 2

1번 기둥	2번 기둥	3번 기둥
1 2
2	1
	1	2
		1 2

 

 예2) n = 3

1번 기둥	2번 기둥	3번 기둥
1 2 3
2 3		1
3	2	1
3	1 2
	1 2	3
1	2	3
1		2 3
		1 2 3

손으로 풀어보기

1. 1번의 n개 중 n - 1개를 3번 기둥을 걸쳐 2번 기둥으로 옮기기
2. 1번의 가장 큰 n을 3번 기둥으로 옮기기
3. 2번의 n - 1개를 1번 기둥을 걸쳐 3번 기둥으로 옮기기를 반복 

슈도코드 작성하기

n(1번 기둥에 있는 원판의 개수)
list(이동한 방법들 리스트)
하노이 함수(n, 1, 2, 3)
answer(n개의 원판을 3번 원판으로 최소로 옮기는 방법)
for(i -> list의 크기만큼) {
    answer[i] = list.get(i)
}
answer 반환

하노이 함수(n, 시작 기둥, 거쳐갈 기둥, 도착 기둥) {
    if(n이 1이라면) {
        list에 [시작 기둥, 도착 기둥] 저장
        return;
    }
    하노이 함수로 1번 기둥의 n - 1개를 3번 기둥을 걸쳐 2번 기둥으로 옮기기
    1번의 가장 큰 n을 3번 기둥으로 옮기므로 list에 [시작 기둥, 도착 기둥] 저장
    하노이 함수로 2번 기둥의 n - 1개를 1번 기둥을 걸쳐 3번 기둥으로 옮기기
}

코드 구현하기

/**
 * 12946) 하노이의_탑
 */
public class L018_12946 {
    // list(이동한 방법들 리스트)
    static List<int[]> list = new ArrayList<>();

    // n(1번 기둥에 있는 원판의 개수)
    public int[][] solution(int n) {
        // 하노이 함수(n, 1, 2, 3)
        hanoi(n, 1, 2, 3);
        // answer(n개의 원판을 3번 원판으로 최소로 옮기는 방법)
        int[][] answer = new int[list.size()][];
        // answer에 방법들 저장
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }
        // answer 반환
        return answer;
    }

    // 하노이 함수(원판의 개수, 시작 기둥, 거쳐갈 기둥, 도착 기둥)
    private void hanoi(int n, int start, int pass, int arrive) {
        // n이 1이라면
        if (n == 1) {
            // list에 [시작 기둥, 도착 기둥] 저장
            list.add(new int[] { start, arrive });
            return;
        }
        // 1번 기둥의 n - 1개를 3번 기둥을 걸쳐 2번 기둥으로 옮기기
        hanoi(n - 1, start, arrive, pass);
        // 1번의 가장 큰 n을 3번 기둥으로 옮기므로 list에 [시작 기둥, 도착 기둥] 저장
        list.add(new int[] { start, arrive });
        // 2번 기둥의 n - 1개를 1번 기둥을 걸쳐 3번 기둥으로 옮기기
        hanoi(n - 1, pass, start, arrive);
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L018_12946 solution = new L018_12946();

        int n = 2;

        int[][] result = solution.solution(n);

        System.out.println(Arrays.toString(result));
    }
}