재귀호출(Recursion) - 하노이탑

시작하며

다른 알고리즘 문제들을 풀면서 재귀가 활용되는 것을 많이 보았다. 또한, 하노이의 탑은 내가 코딩테스트를 처음 준비할때부터 만났던 문제이고 재귀를 모르는 상태에서는 전혀 손대기 어려워서 이번에 재귀 개념을 잡을겸 다른사람의 풀이를 보고 문제를 풀어봤다.

하노이의 탑

문제

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

접근방법

참고한 풀이

https://shoark7.github.io/programming/algorithm/tower-of-hanoi
(접근방법이 정말 자세하고 명쾌하다.. 짱이신듯)

풀이

문제 정의
: N개의 원반을 모두 3번으로 옮겨라 (최소횟수)

여기서 최소횟수가 중요한 것이 아니다. 이미 문제에서 최소횟수 구하는 로직은 기술해놨고 우리는 그것을 어떠한 규칙을 가진 함수로 만들어서 코드를 작성하면 된다.

3개의 원반이 주어졌다고 하자.
문제에서 주어진 해결과정을 세 파트로 나눌 수 있다.

1. 1의 3개 원반을 3으로 모두 옮기기 위해서는 먼저 A,B 원반을 2번으로 옮겨야한다. (3을 거쳐서)
2. C 원반을 3번으로 옮긴다.
3. 2에 있는 A,B 원반을 3으로 옮긴다. (1을 거쳐서)

이를 수식으로 나타내보자.

Hanoi ( N=3, from=1, to = 3 )
= Hanoi ( N=2, from=1, to = 2 )
+move ( N=1, from =1, to = 3 )
+Hanoi ( N=2, from=2, to = 3 )

여기서 Hanoi와 move를 구분한 이유는
1,3은 한번에 옮길수 없어 거쳐서 옮기는 것이고
2는 한번에 옮기기 때문이다.

이것을 추상적인 식으로 일반화해보자.

Hanoi ( N, from, to , via )
= Hanoi ( N-1 , from, via )
+move ( N-2, from, to )
+Hanoi ( N-1, via, to )

** N을 갯수로 정의할수도 있지만 N번째 원반이라고 정의할수도 있다. 이를 반영하면... ( N개를 옮기는 것은 결국 제일 밑에 있는 N번째 원반을 옮기는 것 )

( 사실 여기서 N-2가 나온것에 동공지진.. 당황했었는데 위와 같이 정의하면 깔끔해졌다 .. 다른 항(?)이 나오는 것 최소화하는 것이 좋은듯.. )

따라서 다시 정리하면...

Hanoi ( N, from, to , via )
= Hanoi ( N-1 , from, via , to )
+move ( N, from, to )
+Hanoi ( N-1, via, to , from )

이로써 재귀함수를 사용하여 문제를 정의하게 되었다.

마지막으로, 재귀 호출에서 가장 중요한 것은 무한(?)호출을 멈추는 break 조건이다.

만일 Hanoi 함수에서 N번째 원반을 옮기는 것은 move 함수와 같을 것이다.

Hanoi ( N, from, to , via )
= move ( N, from, to ) ( if N==1 )

이로써 문제는 다 풀었다. 끝. 이 아니라.. 제출은 해야하므로..

문제에서 요구하는 결과값 만들기

이제 문제에서 결과값으로 요구하는 것이 무엇인지 살펴보자.

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

| n | result |
| 2 | [ [1,2], [1,3], [2,3] ] |
| 3 | [ [1,3] , [ 1,2],[3,2] ,[1,3] ,[2,1] ,[2,3], [1,3]]|

위와 같이 원반을 옮길때 마다, 어디서(from) 어디로 (to) 옮겼는지를 결과로 제출하면 되는 문제다.

우리는 move 함수를 이용해 요구하는 형식대로 결과를 완성하면 된다!

완성한 move 함수는 어떤 원반이 이동했는지 까지도 정보을 담고 있으므로 문제가 무엇을 요구하든 문제없다.

여기까지는 괜찮았다..
그런데.. 자바코드를 작성하는데 예상치못하게 애를 먹었다..
(기초 문법 및 개념 부족.. )

코드

import java.util.ArrayList;

class Solution {
    
    //public int[][] result = new int[][];
    public static ArrayList<int[]> result = new ArrayList<>();
    //public static int i = 0 ; 
    
    public int[][] solution(int n) {
        
        hanoi(n,1,3,2);
        
        int[][] answer = new int[result.size()][2]; //size has private access in ArrayList
       
        for(int i = 0 ; i < result.size(); i++){
            answer[i] = result.get(i);
        }
        
        return answer;
    }
    
    public static void move(int n, int from, int to){
        int[] movement = {from, to};
        //result[i++] = movement;
        result.add(movement);
    }
    
    public static void hanoi(int n, int from, int to, int via){
        
        if(n == 1){
            move(n, from, to);
            return;
        } 
        
        hanoi(n-1, from, via, to);
        move(n, from, to);
        hanoi(n-1, via, to, from);
        
    }
}

내가 위 코드를 작성하기 까지 직면한 문제들은 아래와 같다.

1) 2차원 배열 개념 다 까먹음 (int[3][2]가 [int[2],int[2],int[2]] 인 것을 몰랐음..)
2) ArrayList 개념 ( size는 속성이 아니라 size() 메서드로 접근해야함 / ArrayList <-> 배열 변환 )
3) 접근제어자 public , static ( 같은 클래스내 메서드 및 변수 참조에 static 빼먹음 )

꾸역꾸역 검색을 통해 완성했지만.. 실제 코딩테스트에서는 이런 지식들을 찾아볼 수 없고 , 이를 떠나 자바 개발자로서 기본 문법은 반드시 숙지해야하므로... 문법 제대로 공부하길.. ( ArrayList랑 배열 변환은 언제까지 검색할건데..? )

마무리하며

• 다른 사람 풀이를 보며 느낀점..

이제껏 문제를 잘못 풀고 있었다는 생각이 든다. 문제가 요구하는 형식을 어떻게 맞출 것인가에 집중했는데 참고한 풀이에서는 문제의 핵심 원리를 파악하고 문제를 풀면 그 안에서 문제가 요구하는 결과값을 충분히 찾아낼 수 있었다.

근데 이 부분은 문제를 좀 더 풀어봐야 알것 같다. 이 문제는 정말 딱 ‘재귀’라는 핵심 개념이 존재하고 답도 반드시 이것을 이용해서 풀어야하기 때문이다.

무슨 방법을 쓰든 문제를 푸는 것 자체가 중요한지, 좋은 알고리즘이 있다면 그것을 적극 이용해서 푸는 것이 중요한지.. ( 뭐지 벌써 답이 나온거같은... ㅋㅋㅋ )
( 면접 시험가서도 문제 못풀어도 아 이거 oo 개념으로 풀면 될것같습니다. 라고 하는게 어거지로 for문 돌려서 푸는것보다 합격가능성이 높을지도? )

• 코드를 작성하며 느낀점..

알고리즘을 Java 코드로 작성하면서 자바 문법 기초가 부족함을 깨달았다. 다시 책보면서 문법이랑 개념정리 좀 하고 기초를 소홀히 하면 안되겠다.