[Lv.2] 하노이의 탑 : Java

프로그래머스

 

 

 

이해하기

강의에서도 분명 들었던 하노이의 탑 문제...!

보자마자 아 나 이거 아는데 분명 풀었는데 싶었지만... 역시나 못 풀었죠?

 

유일하게 떠올랐던 건 하노이의 탑 규칙 중에 n이 짝수면 첫 move를 2로 하고, n이 홀수면 첫 move를 3으로 한다는 점...

 

이번에 참고한 글은 바로 요 블로그!

[재귀] java 코드로 하노이 탑 쉽게 이해해보자! by.펜잡이 개발자

예시까지 들어가며 자세히 설명해주셔서 이해하는데 도움이 되었다!

하지만 흐름을 이해한 후 그걸 가지고 로직을 만드는게 너무 어려운 것 같다ㅜ

 

 

문제풀이

import java.util.*;

class Solution {
    List<int[]> arr = new ArrayList<>();

    public int[][] solution(int n) {
        hanoi(n, 1, 2, 3);
        int[][] answer = arr.stream().toArray(int[][]::new);
        return answer;
    }

    public void hanoi(int cnt, int start, int mid, int end) {
        if (cnt == 0) {
            return;
        }
        
        hanoi(cnt - 1, start, end, mid);
        arr.add(new int[]{start, end});
        hanoi(cnt - 1, mid, start, end);
    }
}

 

일단 결과를 저장할 List를 선언한다.

stream을 사용하여 바로 int 배열로 만드는 방법을 처음 알게 되었다.

그동안은 for문을 돌며 하나씩 저장해줬는데 더 쉬운 방법이 있었다니, 코드를 줄이는데 도움이 될 것 같다!

 

2층짜리 hanoi 탑을 가지고 hanoi 함수에 적용해보면 다음과 같다.

 

1. hanoi(2, 1, 2, 3)

cnt = 2, start = 1, mid = 2, end = 3

 

위 블로그에서 이 부분은 아직은 움직임이 없기에 'start에서 end로 옮길 것이다.' 라는 식으로만 이해하고 넘어가라고 하셨다. 그렇게 이해하니 좀 더 쉬워보이는...

 

2. if (cnt == 0) 

false라서 다음으로 넘어간다.

 

3. hanoi(1, 1, 3, 2)

cnt = 1, start = 1, mid = 3, end = 2

 

이 부분처럼 재귀로 들어갈 때 start, mid, end의 값이 바뀌는 것이 어렵게 느껴졌다. (체크!)

 

4. if (cnt == 0)

false라서 다음으로 넘어간다.

 

5. hanoi(0, 1, 2, 3)

cnt = 0, start = 1, mid = 2, end = 3

 

6. if (cnt == 0)

return! 3번 이후로 되돌아간다.

 

7. arr.add(new int[]{start, end})

3번에서 start = 1, end = 2이기에 arr에 {1, 2}가 저장된다.

 

8. hanoi(0, 3, 1, 2)

 

9. if (cnt == 0)

return! 2번 이후로 되돌아간다.

 

10. arr.add(new int[]{start, end})

1번에서 start = 1, end = 3이기에 arr에 {1, 3}이 저장된다.

 

11. hanoi(1, 2, 1, 3)

cnt = 1, start = 2, mid = 1, end = 3

 

12. if (cnt == 0)

false라서 다음으로 넘어간다.

 

13. hanoi(0, 2, 3, 1)

 

14. if (cnt == 0)

return! 11번 이후로 되돌아간다.

 

15. arr.add(new int[]{start, end})

11번에서 start = 2, end = 3이기에 arr에 {2, 3}이 저장된다.

 

16. hanoi(0, 1, 2, 3)

 

17. if (cnt == 0)

return! 16번 이후로 되돌아가기에 여기서 끝나게 된다.

 

결과적으로 arr에는 {{1, 2}, {1, 3}, {2, 3}}이 저장된다.

 

 

하노이의 탑은 자주 나오지만 항상 로직 짜는 것이 어려운 것 같다.

자주 나오는만큼 아예 외워버리는 것이 답일수도 있겠다는 생각이 든다 ㅎ...