[PRO] 하노이의 탑 | Java

문제

프로그래머스 코딩테스트 연습 > 연습문제 > 하노이의 탑 | Lv.2

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

프로그래머스

• 알고리즘 분류 : 재귀

 

 

 

풀이 과정

* 유사한 문제의 파이썬 풀이를 하단에 링크 첨부하였습니다.

 

자바 풀이

class Solution {
    public int idx = 0;
    // answer에 이동 저장할 인덱스 
    public int[][] solution(int n) {
        int num = (int)Math.pow(2, n) - 1;
        // 이동 횟수는 2**n - 1
        int[][] answer = new int[num][2];

        hanoi(n, 1, 3, 2, answer);
        return answer;
    }
    
    
    public void hanoi(int n, int start, int end, int tmp, int[][] answer) {
        if(n == 1) {
            int[] move = new int[] {start, end};
            answer[idx++] = move;
            return;
            // n이 1이 되면 start에서 end로 이동한 후 return 
        }
        
        hanoi(n-1, start, tmp, end, answer);
        // 현재 이동할 가장 아래 원판을 제외한 n-1개의 원판에 대해 start에서 tmp로 이동해서 재귀 호출 
        answer[idx++] = new int[] {start, end};
        // 가장 아래 원판을 start에서 end로 이동
        hanoi(n-1, tmp, end, start, answer);
        // n-1개의 원판을 tmp에서 end로 이동하는 재귀함수 호출
    }
}

• 가장 아래에 있는 큰 원판을 start(1)에서 end(3)으로 이동하고, 나머지 n-1개의 원판에 대해 재귀함수를 통해 반복하는 구조이다.
  즉, 가장 큰 원판 하나를 제외한 n-1개의 원판들은 tmp(2)에 임시로 두고 하나의 원판을 이동한 뒤, tmp에 있는 n-1개의 원판에 대해 다시 tmp에서 end로 이동하도록 하는 것이다.
• 하노이의 탑 문제를 풀어봤다고 생각했는데 푼 적이 없어서 아이디어를 떠올리는 데 어려움을 느끼고 구글링을 통해 참고하였다.
  특히 자바의 경우 파이썬과 달리 배열의 크기를 미리 알아야 하기 때문에 이동 횟수를 먼저 계산해줘야 한다.

 

 

백준 하노이 탑 문제에 대한 파이썬 풀이

https://eunjng.tistory.com/42

[BOJ] 하노이 탑 | Python