[java/python] 프로그래머스 Lv2. - 하노이 탑

코딩테스트 연습 - 하노이의 탑 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

이전에 백준에서 똑같은 문제를 풀었을 때 잘 이해가 가지 않았는데

이번에 다시 풀어보니 이해가 갔던 문제였다.

 

재귀함수의 기본인 하노이탑 문제를 정리해보았다.

 

1. 원반 n개를 가장 오른쪽 기둥으로 모두 옮겨야 한다.

2. 한 번에 하나씩만 옮길 수 있다.

3. 크기가 큰 원반 위에 작은 원반을 올려야 한다.

 

이 사항들을 지키며 주어진 원반을 옮겨야 한다.

문제에서는 최소로 움직이는 경로를 구해야하는데

재귀함수를 이용하여 풀면 된다.

원반이 1개 있을 경우, 바로 1->3 기둥으로 옮기면 된다.

2개 있을 경우 1->2 1->3 2->3 기둥으로 옮기면 된다.

3개 있을 경우 가장 큰 원반을 제외한 나머지 원반들을 기둥 2로 옮기고

큰 원반을 3으로 옮긴 후 기둥 2에 있던 원반들을

다시 3으로 옮긴다.

 

정리하자면

1. n-1개의 원반들을 기둥 2로 옮긴다.

2. 기둥 1의 가장 큰 원반을 기둥 3으로 옮긴다.

3. 기둥 2의 원반을 기둥 3으로 옮긴다.

 

이제 이 공식을 활용하여 재귀함수를 작성하면 문제를 해결할 수 있다.

 

[pytyon]

def solution(n):
    answer = []
    hanoi(n,1,3,2,answer)
    return answer
    

def hanoi(n, rod1, rod3, rod2, answer):

    if n == 1: 
        answer.append([rod1,rod3])
    
    else:
        hanoi(n-1, rod1, rod2, rod3, answer)

        answer.append([rod1,rod3])

        hanoi(n-1, rod2, rod3, rod1, answer)

 

 

[java]

import java.util.*;
 
class Solution {
    
    ArrayList<int[]> list;
    
    public int[][] solution(int n) {
        list = new ArrayList<>();
        hanoi(1, 3, 2, n);
        int[][] result = new int[list.size()][2];
        for(int i = 0; i < list.size(); i++) {
            result[i][0] = list.get(i)[0];
            result[i][1] = list.get(i)[1];
        }
        return result;
    }
    
    public void hanoi(int rod1, int rod3, int rod2, int n) {
        int[] move = {rod1, rod3};
        
        if(n == 1) list.add(move);
        else {
            hanoi(rod1, rod2, rod3, n - 1);
            list.add(move);
            hanoi(rod2, rod3, rod1, n - 1);
        }
    }
}