하노이의 탑

 

 

---

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

프로그래머스

---

재귀 함수 연습하려고 문제를 골랐다.

 

뭔가 규칙이 있을까 싶은데.. 정한 시간 시간은 지났다. 규칙 못 찾겠다.

큰 수를 다른 자리로 보내기만 하면 되나봄

n == 3일 때는 3기둥으로 1을 보내야, 마지막에 3기둥에 최소의 움직임으로 탑이 쌓아짐

n == 4일 때는 2기둥으로 1을 보내야, 마지막에 3기둥에 최소의 움직임으로 탑이 쌓아짐

 

처음에는 1을 어느 기둥으로 먼저 보내야할지를 고민을 했었는데.. 

1을 보내는 기둥의 시작점은 중요하지 않다.

그냥 나중에 스왑만 한다고 생각하면 되니..

 

---

 

해결 코드

흠 솔직히 잘 모르겠다. 이건 내 머리에서 나온 방식이 아니다.

이해가 잘 되지 않아서 우선은 외워본다.

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

public class 하노이의탑_2 {

    public static void main(String[] args) {
       Solution solution = new Solution();
       int n = 3;
       int[][] result = solution.solution(n);
       System.out.println(Arrays.toString(result));
       int[][] result2 = new int[][] {{1, 3}, {1, 2}, {3, 2}, {1, 3}, {2, 1}, {2, 3}, {1, 3}};


    }

    static class Solution {
       int k = 0; // 이동 횟수를 저장할 변수

       public int[][] solution(int n) {
          // 결과를 저장할 리스트 초기화
          List<int[]> result = new ArrayList<>();

          // 하노이 탑 알고리즘 실행
          hanoi(n, 1, 3, 2, result);

          // 리스트를 이중 배열로 변환
          int[][] answer = new int[result.size()][2];
          for (int i = 0; i < result.size(); i++) {
             answer[i] = result.get(i);
          }

          // 이동 횟수 출력
          System.out.println("총 이동 횟수: " + k);

          return answer;
       }

       // 하노이 탑 재귀 함수
       private void hanoi(int n, int from, int to, int via, List<int[]> result) {
          if (n == 1) {
             result.add(new int[] {from, to});
             k++; // 이동 횟수 증가
          } else {
             hanoi(n - 1, from, via, to, result); // 위의 n-1개를 from에서 via로 이동
             result.add(new int[] {from, to});
             k++; // 이동 횟수 증가
             hanoi(n - 1, via, to, from, result); // 위의 n-1개를 via에서 to로 이동
          }
       }
    }


}// one class end