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

프로그래머스 하노이의 탑

문제풀이

하노이의 탑은 재귀의 기초 문제로 널리 쓰이는 문제다. 그만큼 재귀의 특성을 잘 담고있는 문제기 때문에 제대로 알아둘 필요가 있다. 이 보다 더 잘 정리한 글이 있을까?

위 링크의 글에서 간단하게 핵심만 요약하자면

• 기저 사례는 다음과 같다.
  • n이 1일 때
    • 출발지의 원판을 도착지로 옮긴다.
  • 나머지의 경우
    • 출발지에 있는 n - 1개의 원판을 경유지로 옮긴다.
    • 출발지에 있는 한 개의 원판을 도착지로 옮긴다.
    • 경유지에 있는 n - 1개의 원판을 도착지로 옮긴다.
• n개의 원판을 옮기기 위한 이동 횟수는 2^n - 1이다.

구현코드

import java.util.*;

class Solution {
    
    ArrayList<int[]> seq;
    public int[][] solution(int n) {
        seq = new ArrayList<>();
        
        hanoi(n, 1, 3, 2);
        
        int[][] answer = new int[seq.size()][2];
        for(int i = 0 ; i < seq.size() ; ++i){
            int[] cmd = seq.get(i);
            answer[i][0] = cmd[0];
            answer[i][1] = cmd[1];  
        }
        
        return answer;
    }
    
    private void hanoi(int n, int from, int to, int via){
        int[] move = {from, to};
        
        if(n == 1) {
            seq.add(move);
        } else {
            hanoi(n - 1, from, via, to);
            seq.add(move);
            hanoi(n - 1, via, to, from);   
        }
    }
}