[Programmers] 하노이의 탑 (Java / Python)

문제링크

문제 설명

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

한 번에 하나의 원판만 옮길 수 있습니다.
큰 원판이 작은 원판 위에 있어서는 안됩니다.
하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.

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

제한사항

n은 15이하의 자연수 입니다.

 

입출력 예

n	result
2	[[1, 2], [1, 3], [2, 3]]

문제풀이

하나씩 옮기다 보면 규칙을 알 수 있다. 가장 큰 원판이 n이고 원판들이 1 부터 n 순서대로 쌓여있는 것을 n- 라 부른다면, n 을 옮기기 위해서는 (n - 1)- 들을 옮겨야 했다. 따라서 n = 5 일 때, 다음과 같은 규칙을 생각해볼 수 있었다.

목표: 5- 를 기둥 1에서 기둥 3으로
=> 4-를 기둥 1에서 기둥 2로
==> 3-를 기둥 1에서 기둥 3으로
===> 2-를 기둥 1에서 기둥 2로
====> 1- 를 기둥 1에서 기둥 3으로
====> 크기 1 원판을 기둥 1에서 기둥 3으로 (V)
===> 크기 2 원판을 기둥 1에서 기둥 2로 (V)
====> 1- 를 기둥 3에서 기둥 2로
==> 크기 3 원판을 기둥 1에서 기둥 3으로 (V)
===> 2- 를 기둥 2에서 3으로
=> 크기 4 원판을 기둥 1에서 기둥 2로 (V)
==> 3- 를 기둥 3에서 기둥 2
크기 5 원판을 기둥 1에서 기둥 3으로 (V)
=> 4- 를 기둥 2에서 3으로

위와같은 규칙은, 재귀로 표현될 수 있다. (V)로 표시된 부분을 제외하고는, 모두 재귀함수를 호출하는 부분인 것이다. 실제로 동작을 하게되는 부분은 (V)가 된다. 호출될 때 필요한 정보들을 보면, 가장 큰 크기(n), 시작 위치, 다음 위치, 목표위치가 있다.

 

코드

Java

import java.util.*;

public class TowerOfHanoi {

    private int index;
    private int[] currPos;
    private int[][] answer;

    public int[][] solution(int n) {
        index = 0;
        currPos = new int[n + 1];
        Arrays.fill(currPos, 1);
        answer = new int[(int) Math.pow(2, n) - 1][];
        dfs(n, 3);

        return answer;
    }

    private void dfs(int n, int to) {
        if (n == 1) {
            answer[index++] = new int[] {currPos[n], to};
            currPos[n] = to;
            return;
        }

        dfs(n - 1, nextTo(n, to));
        answer[index++] = new int[] {currPos[n], to};
        currPos[n] = to;
        dfs(n - 1, to);
    }

    private int nextTo(int n, int to) {
        for (int i = 1; i <= 3; i++) {
            if (currPos[n] != i && to != i) return i;
        }
        return -1;
    }
}

Python

def solution(n):
    return dfs(n, 1, 2, 3, [])

def dfs(n, start, via, to, answer):
    if n == 1:
        answer.append([start, to])
        return answer
    
    answer = dfs(n - 1, start, to, via, answer)
    answer.append([start, to])
    return dfs(n - 1, via, start, to, answer)