[프로그래머스] 하노이의 탑

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12946

프로그래머스

 

문제 분석

[제한사항]

• n은 15이하의 자연수 입니다.

 

하노이 탑의 규칙에 맞게 1번 기둥에 있는 원판들을 3번 기둥에 옮기는 방법을 리턴하는 문제이다.

 

1. 한 번에 하나의 원판만 옮길 수 있다.

2. 큰 원판이 작은 원판 위에 있어서는 안된다.

 

문제 접근

이 문제를 풀기 위해서는 큰 문제를 나눠 작은 문제로 만들어야 한다.

 

제일 큰 원반을 n 번 원반이라 하고 가장 작은 원반을 1번 원반이라고 해보자.

1번 기둥에 있는 n개의 원반을 모두 3번 기둥에 옮기기 위해서는 다음과 같은 작업이 필요하다.

1. (n-1 번 ~ 1번) 원반을 2번 기둥에 옮긴다.
2. n번 원반을 3번 원반에 옮긴다.
3. 2번에 있는 (n-1 번 ~ 1번) 원반을 3번 기둥으로 옮긴다.

위의 방식을 재귀로 구현하면 된다.

코드

import java.util.*;

class Solution {
    public static List<int[]> list = new ArrayList<>();
    
    public int[][] solution(int n) {
        hanoi(1, 2, 3, n);
        int[][] answer = new int[list.size()][2];

        for(int i=0; i<list.size(); i++){
            answer[i] = list.get(i);
        }
        return answer;
    }
    
    public void hanoi(int start, int mid, int target, int n){
        if(n == 1){
            list.add(new int[]{start, target});
            return;
        }
        
        hanoi(start, target, mid, n - 1);
        hanoi(start, mid, target, 1);
        hanoi(mid, start, target, n - 1);
    }
}