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

 

문제

프로그래머스

 

알고리즘

없음

 

풀이

n개의 원판을 1번에서 3번으로 옮기려면

제일 큰 원판을 제외한 n-1개의 원판을 2번으로, 제일 큰 원판을 3번으로 옮긴 후

2번에 있던 n-1개의 원판들을 다시 3번으로 옮겨야한다.

 

이를 위해서 n-1 개의 원판을 1번에서 2번으로 옮기는 작업이 필요한데

이는 위와 마찬가지로 제일 큰 원판을 제외한 n-2개의 원판을 3번으로 옮기고, 제일 큰 원판을 2번으로 옮긴 후

3번에 있던 나머지 n-2개의 원판들을 다시 2번으로 옮겨야한다.

 

결국 n개의 원판을 옮기는 문제는 1개의 원판을 옮기는 문제로 분해된다.

따라서 재귀적으로 원판들을 임시 기둥으로 옮기고 옮긴 기둥 번호를 리스트에 삽입한 후 임시 기둥에서 최종 기둥으로 원판을 옮긴다.

 

 

코드

import java.util.*;

class Solution {
    ArrayList<Integer[]> answer;
    public ArrayList<Integer[]> solution(int n) {
        answer = new ArrayList<>();
        
        hanoi(n, 1, 2, 3);
        return answer;
    }
    
    public void hanoi(int n, int start, int temp, int end) {
        if(n==0) return;
        
        hanoi(n-1, start, end, temp);
        answer.add(new Integer[]{start, end});
        hanoi(n-1, temp, start, end);
    }
}