catsridingCATSRIDING|OCEANWAVES
Challenges

프로그래머스 | Level 2 | 하노이의 탑

jynn@catsriding.com
Sep 30, 2024
Published byJynn
999
프로그래머스 | Level 2 | 하노이의 탑

Programmers | Level 2 | 하노이의 탑

Problems

  • 📘 Src: Programmers
  • 🗂️ Cat: Divide and Conquer

󰧭 Description

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

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

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

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

 Constraints

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

󰦕 Examples

nresult
2[[1, 2], [1, 3], [2, 3]]

Solutions

󰘦 Code

Solution.java
import java.util.*;

class Solution {
    public int[][] solution(int n) {
        List<int[]> moves = new ArrayList<>();  // 모든 이동 경로를 저장할 리스트
        hanoi(n, 1, 3, 2, moves);  // 재귀 함수 호출하여 원판 이동 경로 계산
        return moves.stream().toArray(int[][]::new);  // 리스트를 2차원 배열로 변환하여 반환
    }
    
    // 하노이의 탑 이동을 위한 재귀 함수
    private void hanoi(int n, int from, int to, int temp, List<int[]> moves) {
        if (n == 0) return;  // 기저 조건: 옮길 원판이 없을 때 종료
        
        hanoi(n - 1, from, temp, to, moves);  // n-1개의 원판을 임시 기둥으로 이동
        moves.add(new int[]{from, to});  // 가장 큰 원판을 목표 기둥으로 이동
        hanoi(n - 1, temp, to, from, moves);  // 나머지 n-1개의 원판을 목표 기둥으로 이동
    }
}

 Approaches

하노이의 탑 문제는 주어진 문제를 작은 하위 문제로 나누어 해결하는 분할 정복(Divide and Conquer) 알고리즘에 해당합니다.

1. 문제 분석

하노이의 탑은 재귀적 접근을 통해 문제를 반복적으로 작은 하위 문제로 나누어 해결하는 전형적인 분할 정복 문제입니다. n개의 원판을 최소한의 이동 횟수로 3번 기둥으로 옮기는 것이 목표입니다. 이때, 각 원판을 옮길 때마다 큰 원판을 이동하기 전에 더 작은 원판들을 중간 기둥으로 이동시켜 빈 공간을 확보한 후, 큰 원판을 목적지로 옮기고 다시 작은 원판들을 최종 기둥으로 이동시키는 패턴을 반복합니다.

이 과정에서 재귀 호출을 사용해 매 단계마다 전체 문제를 하위 문제로 나누어 해결합니다. 큰 원판을 옮기기 전까지 나머지 원판들을 중간 기둥으로 이동시키는 작업을 재귀적으로 처리하고, 이후 다시 작은 원판들을 최종 목적지로 옮기며, 하위 문제들을 완성해 전체 문제를 해결하는 방식입니다.

기본적으로, n개의 원판을 이동시키기 위해서는 다음과 같은 접근이 필요합니다:

  1. 가장 큰 원판을 제외한 나머지 n - 1개의 원판을 1번 기둥에서 2번 기둥으로 이동.
  2. 가장 큰 원판을 3번 기둥으로 이동.
  3. 2번 기둥에 있는 n - 1개의 원판을 다시 3번 기둥으로 이동.

이 패턴을 반복하여 모든 원판이 3번 기둥에 쌓이도록 하는 것입니다. 이 과정에서 각 원판의 이동을 추적하여, 최종적으로 모든 이동 경로를 배열로 반환하면 됩니다.

하노이의 탑에서 원판의 개수가 4개인 경우의 이동 과정은 아래와 같습니다:

단계원판 이동 경로1번 기둥2번 기둥3번 기둥
초기출발 → 도착[4, 3, 2, 1][][]
11번 기둥 → 2번 기둥[4, 3, 2][1][]
21번 기둥 → 3번 기둥[4, 3][1][2]
32번 기둥 → 3번 기둥[4, 3][][2, 1]
41번 기둥 → 2번 기둥[4][3][2, 1]
53번 기둥 → 1번 기둥[4, 1][3][2]
63번 기둥 → 2번 기둥[4, 1][3, 2][]
71번 기둥 → 2번 기둥[4][3, 2, 1][]
81번 기둥 → 3번 기둥[][3, 2, 1][4]
92번 기둥 → 3번 기둥[][3, 2][4, 1]
102번 기둥 → 1번 기둥[2][3][4, 1]
113번 기둥 → 1번 기둥[2, 1][3][4]
122번 기둥 → 3번 기둥[2, 1][][4, 3]
131번 기둥 → 2번 기둥[2][1][4, 3]
141번 기둥 → 3번 기둥[][1][4, 3, 2]
152번 기둥 → 3번 기둥[][][4, 3, 2, 1]
2. 접근 방식

하노이의 탑 문제는 재귀적 접근을 통해 해결할 수 있습니다. 재귀적으로 문제를 분할하여 각 원판을 옮기고, 중간 기둥을 경유하면서 최종 기둥으로 이동하는 과정을 반복합니다.

  • 기저 조건 정의: 옮길 원판이 없을 경우, 즉시 종료합니다.
  • 재귀적 이동 패턴 적용: n개의 원판을 1번 기둥에서 3번 기둥으로 이동시키기 위해, 다음과 같은 단계로 재귀적으로 분할하여 해결합니다.
    • 1단계: n - 1개의 작은 원판들을 1번 기둥에서 2번 기둥으로 임시로 이동하여, n번째 가장 큰 원판이 1번 기둥에서 3번 기둥으로 이동할 수 있는 공간을 확보합니다. 이 과정을 통해 큰 원판의 이동을 방해하지 않도록 다른 작은 원판들이 모두 2번 기둥에 정렬됩니다.
    • 2단계: 1번 기둥에 남아있는 가장 큰 원판을 3번 기둥으로 이동합니다. 이때, 2번 기둥에 있는 작은 원판들은 그대로 유지됩니다.
    • 3단계: 2번 기둥에 쌓인 n - 1개의 원판들을 최종 목적지인 3번 기둥으로 이동시켜 전체 원판이 3번 기둥에 최종적으로 정렬되도록 합니다. 이 단계에서는 1번 기둥이 임시 기둥의 역할을 하게 됩니다.
  • 경로 저장: 각 이동 단계에서 원판이 이동하는 출발 기둥과 도착 기둥의 정보를 기록합니다. 이를 2차원 배열에 저장하여 최종적으로 모든 이동 경로를 반환합니다.

이 과정은 재귀적으로 반복되며, 각 단계마다 경로를 추가하면서 모든 원판을 3번 기둥으로 이동시키게 됩니다.

3. 이동 경로 저장 및 재귀 함수 초기화

먼저, 재귀적으로 이동 경로를 기록할 리스트를 초기화하고, 1번 기둥의 모든 원판을 3번 기둥으로 이동시키기 위한 재귀 함수를 호출합니다. 이동 경로를 저장할 리스트는 이후 2차원 배열로 변환하여 최종 결과로 반환됩니다.

이 과정에서 재귀 함수는 총 n개의 원판을 1번 기둥에서 3번 기둥으로 옮기기 위해, 중간 기둥을 경유하면서 순차적으로 이동을 기록합니다.

Solution.java
List<int[]> moves = new ArrayList<>();  // 이동 경로를 기록할 리스트
hanoi(n, 1, 3, 2, moves);  // 재귀 함수 호출
return moves.stream().toArray(int[][]::new);  // 2차원 배열로 변환하여 반환
4. 하노이의 탑 이동 로직 구현

재귀 함수는 각 단계마다 현재 옮겨야 할 원판의 개수를 인자로 받아, 다음과 같은 방식으로 동작합니다.

  1. 기저 조건 처리: 현재 옮길 원판의 수가 0이면 종료합니다. 즉, 더 이상 옮길 원판이 없는 경우입니다.
  2. 1단계: 가장 큰 원판을 제외한 n - 1개의 원판을 1번 기둥에서 2번 기둥으로 이동합니다.
  3. 2단계: 가장 큰 원판을 1번 기둥에서 3번 기둥으로 이동합니다.
  4. 3단계: 나머지 n - 1개의 원판을 2번 기둥에서 3번 기둥으로 이동합니다.

이 과정에서 각 이동을 리스트에 기록하며, 이동 경로는 최종적으로 모든 원판이 3번 기둥에 쌓일 때까지 반복됩니다.

Solution.java
private void hanoi(
        int n,    // 옮길 원판 개수
        int from, // 출발 기둥
        int to,   // 도착 기둥
        int temp, // 임시 기둥
        List<int[]> moves  // 이동 경로 추적
) {
    if (n == 0) return;  // 옮길 원판이 없을 때 종료
    
    // n-1개의 원판을 임시 기둥으로 이동
    hanoi(n - 1, from, temp, to, moves);
    
    // 가장 큰 원판을 목표 기둥으로 이동
    moves.add(new int[]{from, to});
    
    // n-1개의 원판을 목표 기둥으로 이동
    hanoi(n - 1, temp, to, from, moves);
}

재귀 호출은 일반적인 절차적 프로세스와는 달리 그 흐름을 이해하기가 쉽지 않습니다. 특히, 하노이 탑 문제에서는 재귀적으로 여러 단계를 거쳐 원판을 옮기는 과정이 겹치면서 복잡해질 수 있습니다. 원판의 개수가 4개일 때 재귀 호출의 흐름을 구체적으로 살펴보면 다음과 같습니다:

// hanoi(원판 개수, 출발 기둥, 도착 기둥, 임시 기둥)
hanoi(4, 1, 3, 2)
├── hanoi(3, 1, 2, 3)
|   ├── hanoi(2, 1, 3, 2)
|   |   ├── hanoi(1, 1, 2, 3)
|   |   |   ├── hanoi(0, 1, 3, 2) ⛔
|   |   |   ├── moves.add(new int[]{1, 2}) //  1st: 1번 기둥 → 2번 기둥
|   |   |   └── hanoi(0, 3, 2, 1) ⛔
|   |   ├── moves.add(new int[]{1, 3})     //  2nd: 1번 기둥 → 3번 기둥
|   |   └── hanoi(1, 2, 3, 1)
|   |       ├── hanoi(0, 2, 1, 3) ⛔
|   |       ├── moves.add(new int[]{2, 3}) //  3rd: 2번 기둥 → 3번 기둥
|   |       └── hanoi(0, 1, 3, 2) ⛔
|   ├── moves.add(new int[]{1, 2})         //  4th: 1번 기둥 → 2번 기둥
|   └── hanoi(2, 3, 2, 1)
|       ├── hanoi(1, 3, 1, 2)
|       |   └── hanoi(0, 2, 3, 1) ⛔
|       |   └── moves.add(new int[]{3, 1}) //  5th: 3번 기둥 → 1번 기둥
|       |   └── hanoi(0, 3, 1, 2) ⛔
|       ├── moves.add(new int[]{3, 2})     //  6th: 3번 기둥 → 2번 기둥
|       └── hanoi(1, 1, 2, 3)
|           └── hanoi(0, 1, 2, 3) ⛔
|           └── moves.add(new int[]{1, 2}) //  7th: 1번 기둥 → 2번 기둥
|           └── hanoi(0, 2, 3, 1) ⛔
├── moves.add(new int[]{1, 3})             //  8th: 1번 기둥 → 3번 기둥
└── hanoi(3, 2, 3, 1)
    ├── hanoi(2, 2, 1, 3)
    |   ├── hanoi(1, 2, 3, 1)
    |   |   ├── hanoi(0, 2, 1, 3) ⛔
    |   |   ├── moves.add(new int[]{2, 3})  //  9th: 2번 기둥 → 3번 기둥
    |   |   └── hanoi(0, 1, 3, 2) ⛔
    |   ├── moves.add(new int[]{2, 1})      // 10th: 2번 기둥 → 1번 기둥
    |   └── hanoi(1, 3, 1, 2)
    |       └── hanoi(0, 3, 2, 1) ⛔
    |       └── moves.add(new int[]{3, 1})  // 11th: 3번 기둥 → 1번 기둥
    |       └── hanoi(0, 2, 1, 3) ⛔
    ├── moves.add(new int[]{2, 3})          // 12th: 2번 기둥 → 3번 기둥
    └── hanoi(2, 1, 3, 2)
        ├── hanoi(1, 1, 2, 3)
        |   ├── hanoi(0, 1, 3, 2) ⛔
        |   ├── moves.add(new int[]{1, 2})  // 13th: 1번 기둥 → 2번 기둥
        |   └── hanoi(0, 3, 2, 1) ⛔
        ├── moves.add(new int[]{1, 3})      // 14th: 1번 기둥 → 3번 기둥
        └── hanoi(1, 2, 3, 1)
            ├── hanoi(0, 2, 1, 3) ⛔
            ├── moves.add(new int[]{2, 3})  // 15th: 2번 기둥 → 3번 기둥
            └── hanoi(0, 1, 3, 2) ⛔
5. 최종 결과 도출

모든 이동 경로가 리스트에 저장되면, 이를 2차원 배열로 변환하여 반환합니다. 각 이동은 [출발 기둥, 도착 기둥] 형태의 배열로 저장되며, 이를 통해 최종적으로 n개의 원판을 최소 이동 횟수로 옮기는 과정을 완성할 수 있습니다.

Solution.java
// 이동 경로를 2차원 배열 형태로 반환
return moves.stream().toArray(int[][]::new);

󰄉 Complexity

  • ⏳ TC: O(2^n)
  • 💾 SC: O(n)

하노이의 탑 문제는 재귀적으로 모든 이동 경로를 계산해야 하므로, 시간 복잡도는 O(2^n)입니다. 또한, 이동 경로를 저장하기 위한 리스트의 크기가 n에 비례하여 증가하므로, 공간 복잡도는 O(n)입니다.

  • Algorithm
  • Divide and Conquer