[Java / Kotlin] 99 클럽 코딩 테스트 스터디 비기너 7일차 - 하노이의 탑

https://school.programmers.co.kr/learn/courses/30/lessons/12946?language=kotlin

프로그래머스

[문제]

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

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

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

[제한사항]
n은 15이하의 자연수입니다.

 

[입출력]

 

[풀이]

하노이 탑에 대한 알고리즘을 이해하지 못해 제대로 풀지 못한 문제입니다.

먼저 알고리즘을 이해하고, 특정 규칙을 찾아 재귀 방식으로 풀이해야 했습니다.

이 알고리즘에는 규칙 3가지가 있습니다.

1. 한 번에 한 개의 원판만 옮길 수 있다.
2. 가장 위에 있는 원판만 이동할 수 있다.
3. 큰 원판이 작은 원판 위에 있어서는 안 된다.

입출력 예시처럼 원판 2개가 존재하는 가장 단순한 케이스를 생각해 보자면

1. n개 원판 중 n-1 번째를 2번 탑으로 옮깁니다.

2. 남은 1개의 원판을 3번 탑으로 옮깁니다.

3. 이제 다시 n-1 번째 원판을 2번에서 3번 탑으로 옮깁니다.

 

여기서 n-1의 원판이 출발 - 경유 - 도착의 과정을 거치게 되는 것을 확인하실 수 있습니다.

그리고 1번과 3번 상황에서 재귀적으로 n-1의 이동이 발생하게 되죠
결국 n개의 원판이 출발지, 경유지, 도착지로 최종 운반되는 과정을 재귀식으로 출력해야 하는 문제입니다.

 

먼저 자바 풀이입니다.

재귀함수를 구현해 주겠습니다.

 

원판이 한 개 있을 때에는 바로 목적지로 옮겨주면 되겠습니다.

private static List<int[]> resultList;

public static void hanoi(int n, int start, int middle, int end) {
    if (n == 1) {
        resultList.add(new int[]{start, end});
        return;
    }

........................
}

 

첫 번째 상황인 n - 1 번째를 경유지로 옮기는 과정을 고려합니다.

public static void hanoi(int n, int start, int middle, int end) {
    if (n == 1) {
        resultList.add(new int[]{start, end});
        return;
    }

    hanoi(n-1, start, end, middle); //middle을 일단 목적지로
}

 

두 번째 상황인 n 번째를 바로 목적지로 옮기는 과정을 고려합니다.

public static void hanoi(int n, int start, int middle, int end) {
    if (n == 1) {
        resultList.add(new int[]{start, end});
        return;
    }

    hanoi(n-1, start, end, middle); //middle을 일단 목적지로

    resultList.add(new int[]{start, end});
}

 

마지막 상황인 n - 1번째를 경유지에서 목적지로 옮기는 처리를 해주면 됩니다.

public static void hanoi(int n, int start, int middle, int end) {
    if (n == 1) {
        resultList.add(new int[]{start, end});
        return;
    }

    hanoi(n - 1, start, end, middle); //middle을 일단 목적지로

    resultList.add(new int[]{start, end});

    hanoi(n - 1, middle, start, end);
}

 

최종 전체 풀이 코드는 다음과 같겠습니다.

private static List<int[]> resultList;

public static void hanoi(int n, int start, int middle, int end) {
    if (n == 1) {
        resultList.add(new int[]{start, end});
        return;
    }

    hanoi(n - 1, start, end, middle); //middle을 일단 목적지로

    resultList.add(new int[]{start, end});

    hanoi(n - 1, middle, start, end);
}

public static int[][] solution(int n) {

    resultList = new ArrayList<>();
    hanoi(n, 1, 2, 3);

    int[][] answer = new int[resultList.size()][];
    for (int i = 0; i < resultList.size(); i++) {
        answer[i] = resultList.get(i);
    }

    return answer;
}

 

코틀린 풀이는 아래와 같습니다. inner func을 사용했을 뿐 큰 차이는 없습니다.

fun solution(n: Int): Array<IntArray?> {
    val resultList = mutableListOf<IntArray>()

    fun hanoi(n: Int, start: Int, middle: Int, end: Int) {
        if (n == 1) {
            resultList.add(intArrayOf(start, end))
            return
        }

        hanoi(n - 1, start, end, middle) //middle을 일단 목적지로

        resultList.add(intArrayOf(start, end))

        hanoi(n - 1, middle, start, end)
    }

    hanoi(n, 1, 2, 3)

    return resultList.toTypedArray()
}

 

이러한 공식(?) 알고리즘은 이해가 어려우면 경험을 통해 외워두는 것도.. 좋은 방법이라고 생각합니다.