(Java) Programmers 하노이의 탑

 

- 목차

 

문제 소개.

"프로그래머스의 하노이의 탑" 문제의 웹 링크를 하단에 첨부합니다.

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

프로그래머스

 

문제 설명.

하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.

1. 한 번에 하나의 원판만 옮길 수 있습니다.
2. 큰 원판이 작은 원판 위에 있어서는 안됩니다.

하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.

1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.

 

 

문제 분석.

하노이의 탑은 재귀함수와 관련된 아주 유명한 문제입니다.

저 또한 재귀함수를 활용하여 해당 문제에 접근하려고 합니다.

 

여기서 중요한 포인트는 가장 큰 원반이 목적지 기둥으로 옮겨져야 된다는 점입니다.

예를 들어 1,2,3 번 이라는 원반이 존재한다고 가정하겠습니다.

이 경우에 3번 원반이 가장 먼저 목적지 기둥으로 옮겨져야하고, 이를 위해서는 1번 과 2번 원반이 다른 기둥에 위치해야합니다.

그럼 2번 원반이 다른 기둥에 존재하기 위해서는 1번 원반이 시작 기둥이나 목적지 기둥에 있어야합니다.

즉, 이러한 관점에서 재귀적으로 접근할 수 있게 됩니다.

 

쉬운 설명을 위해서 그림으로 나타내보겠습니다.

3개의 기중을 from 기둥, to 기둥, other 기둥으로 표현하겠습니다.

 

3번 원반을 from 기둥에서 to 기둥으로 옮기는 법.

3번 원반을 from -> to 로 옮기기 위해서는 필연적으로 2번 원반이 other 기둥에 있어야합니다.

 

2번 원반을 from 기둥에서 other 기둥으로 옮기는 법.

2번 원반을 from -> other 로 옮기기 위해서는 필연적으로 1번 원반이 to 기둥에 있어야합니다.

 

1번 원반을 from 기둥에서 to 기둥으로 옮기는 법.

1번 원반은 최상단에 위치하기 때문에 그냥 to 기둥으로 옮기면 됩니다.

 

 

 

 

문제 풀이.

 

import java.util.*;

class Solution {
    static List<int[]> history = new ArrayList();        
    public int[][] solution(int n) {
        hanoi(n, 0, 2, 1);
        int[][] answer = new int[history.size()][2];
        for (int i = 0; i < history.size(); i++) {
            int[] position = history.get(i);
            answer[i] = position;
        }
        return answer;
    }
    
    void hanoi(int num, int from, int to, int other) {
        if (num == 0) return;
        hanoi(num - 1, from, other, to);
        history.add(new int[]{from + 1, to + 1});
        hanoi(num - 1, other, to, from);
    }
}