하노이의 탑 - 프로그래머스

Yuno·2024년 7월 20일

Java)코테 연습

목록 보기

15/18

하노이의 탑은 고전적인 재귀 문제로 잘 알려져있다.
이전에도 제로베이스 에서 학습한적이 있는데
아직 해당 알고리즘이 이해가 되지 않아 다시 학습을 하며 참고했다.

문제 접근 방식

한번에 하나의 원판만 이동 가능

원판의 갯수가 짝수이면, 첫번째 원판은 중간 기둥에 놓는다.

원판의 갯수가 홀수이면, 첫번째 원판은 마지막 기둥에 놓는다.

마지막 원판은 무조건 마지막 기둥에 있어야 한다.

원판을 이동하기 위해 하위 문제로 원판을 나누고 재귀적으로 호출한다.

📌정적 변수 선언

$solution$ 메서드와 $hanoi$ 메서드에서 같이 접근할수 있는 List 변수를 선언했다.
해당 List에서 이동 기록을 저장한다.

public static List<int[]> list;

📌 $hanoi$ 메서드

원판의 개수를 받은 n
시작 기둥인 from
중간 기둥인 sub
마지막 기둥인 to

public static void hanoi(int n, int from, int sub, int to)

마지막 원판은 무조건 from 기둥에서 to 기둥으로 간다.

if (n == 1) {
   list.add(new int[]{from, to});
   return;
}

n - 1 번째의 원판을 보조 기둥으로 이동
현재 기둥에서 목표 기둥으로 가장 큰 원판을 이동
마지막으로 n - 1 개의 원판을 보조 기둥에서 목표 기둥 으로 이동

hanoi(n - 1, from, to, sub);
list.add(new int[]{from, to});
hanoi(n - 1, sub, from, to);
}

📌 $solution$ 메서드

list를 ArrayList 로 초기화 하고(동적 리스트로 받기 위해) $hanoi$ 함수를 호출하여 원판을 이동시킨다.

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

list에 저장된 이동 기록을 2차원 정수형 배열에 저장한다.

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

시각적으로 이해하기

n = 2

해당 코드는 넘어간다 (현재 $n$ 은 2 이기 때문)

if (n == 1) {
   list.add(new int[]{from, to});
   return;
}

해당 코드를 만나면서 시작 (이때 분할된다.)

hanoi(n - 1, from, to, sub); // 1, 1, 3, 2

$n$ 은 1 이므로 재귀호출되어 해당 코드로 돌아온다.

if (n == 1) {
   list.add(new int[]{from, to}); // 1, 2
   return;
}

리스트에 저장 (분할된 코드는 여기서 따로 저장)

list.add(new int[]{from, to}); // 1, 3

분할된 코드는 해당 코드를 만나며 한번더 위치 교환

hanoi(n - 1, sub, from, to); // 1, 2, 1, 3

$hanoi$ 함수 호출 흐름

hanoi(2, 1, 2, 3)
  - hanoi(1, 1, 3, 2)
      - list.add(new int[]{1, 2})
  - list.add(new int[]{1, 3})
  - hanoi(1, 2, 1, 3)
      - list.add(new int[]{2, 3})

표로 이동을 구현했을 때

n	f	s	t
2	1	2	3
1	1	3	2
2	1	2	3
1	2	1	3

1번째, 3번째가 분기점

{{1, 2}, {1, 3}, {2, 3}}

재귀 트리 구조

hanoi(n, from, sub, to)
    -> hanoi(n-1, from, to, sub)
    -> move largest from `from` to `to`
    -> hanoi(n-1, sub, from, to)

n = 3 일때 재귀 트리 구조

hanoi(3, 1, 2, 3)
|
|- hanoi(2, 1, 3, 2)
   |
   |- hanoi(1, 1, 2, 3)
   |- move 1 from 1 to 2
   |- hanoi(1, 3, 1, 2)
|- move 2 from 1 to 3
|- hanoi(2, 2, 1, 3)
   |
   |- hanoi(1, 2, 3, 1)
   |- move 2 from 2 to 3
   |- hanoi(1, 1, 2, 3)

💻 최종 코드 💻

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public static List<int[]> list;

    public int[][] solution(int n) {
        list = new ArrayList<>();
        hanoi(n, 1, 2, 3);


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

        return answer;
    }

    public static void hanoi(int n, int from, int sub, int to) {
        if (n == 1) {
           list.add(new int[]{from, to});
           return;
        }

        hanoi(n - 1, from, to, sub);
        list.add(new int[]{from, to});
        hanoi(n - 1, sub, from, to);
    }

    public static void main(String[] args) {
        int n = 15;
        Solution sol = new Solution();
        int[][] arr = sol.solution(n);
        System.out.println(Arrays.deepToString(arr));
    }
}

👉재귀호출

해당 코드를 예시로, $n$ 이 커질수록 재귀 트리의 깊이와 폭은 급격히 증가한다.
$n$ 이 증가할때 마다, 재귀 호출이 $2^n - 1$ 만큼의 이동을 필요로 한다.
해당 문제의 제한조건인 $n = 15$ 인 경우에는
$2^{15} - 1 = 32767$ 총 32767번의 이동이 필요로 하게 된다.

해당 코드로 확인해본 결과 32767번의 계산 횟수가 확인되었다.

public class Main {
    public static int hanoi(int n, int from, int sub, int to) {
        if (n == 1) {
            return 1;
        }
        int cnt = 0;
        cnt += hanoi(n - 1, from, to, sub);
        cnt++;
        cnt += hanoi(n - 1, sub, from, to);

        return cnt;
    }

    public static void printHanoi(int n) {
        System.out.println(hanoi(n, 1, 2, 3));
    }
    public static void main(String[] args) {
        int n = 15;
        printHanoi(n); // 32767
    }
}