백준 11729번 : 하노이 탑 이동 순서 with 재귀함수 잘 설계하는 법

출처 :야, 너두 재귀할 수 있어: 재귀가 풀리는 4단계 접근법 (velog.io)

---

재귀함수 잘 설계하는 법

1. 마인드 세팅 : 함수의 흐름을 생각하지 말고, 큰 그림에 집중하기

재귀 함수를 잘 설계하기 위한 제 1 원칙은 '재귀적으로 생각하지 말기'이다.

• ❗함수의 실행 흐름과 콜스택을 그대로 따라가려하지 말자.❗ => 특히 내가 많이 하는 실수
• 특정 단계에서 이전 단계와 조합되어 어떻게 작동하는지에만 집중하자.
• 함수를 호출할 때마다 베이스 조건에 가까워져야 한다.
• 그 전 단계에서 무조건 정답이 리턴되었다고 믿자. 그리고 그 이상은 생각하지 말자.
  이걸 '재귀적 믿음의 점프'라고도 부른다.
  (이런 용어가 있을 정도로 하나의 단계에 대해서만 생각하고, 
  이전 단계는 이미 정답이라 믿는 것이 재귀함수를 풀이하는 일반적인 방법임)

위의 마인트를 탑재했다면, 아래 방법으로 재귀함수를 만들어주면 된다.

2. 재귀함수 설계 순서

• 큰 그림 하나만 생각한다.
• 이전 단계 재귀함수를 어떤 상황에서 어떤 용도로 호출할 것인지를 생각한다. (점화식으로 생각하면 쉬움)
• 베이스 조건 (가장 간단한 경우) 무엇을 리턴할지 생각한다.

사실 위에 정리한 내용은 내가 내 언어로 바꾼 것이고, 정말로 잘 정리된 방법론은 아래 블로그를 참고하자.
https://velog.io/@eddy_song/you-can-solve-recursion

야, 너두 재귀할 수 있어: 재귀가 풀리는 4단계 접근법

그럼 위 내용을 생각하면서 하노이 탑 문제를 풀어보자.

---

문제

11729번: 하노이 탑 이동 순서 (acmicpc.net)

11729번: 하노이 탑 이동 순서

---

아이디어

1. 큰 그림 하나만 생각하기
하노이탑은 n개의 원판을 start기둥에서 mid기둥을 이용해서 to기둥로 이동시키는 패턴을 갖는다.
이를 hanio(n,start,mid,to)함수라고 하자.

2. 이전 단계 재귀함수를 어떤 상황에서 어떤 용도로 호출할 것인가.
이전 단계 재귀함수는 가장 큰 원판 하나를 제외한 n-1개 원판을 옮기는 함수이다.
하노이 퍼즐을 풀는 과정은 아래와 같다.
- n-1개를 n단계 기준 start에서 to를 거쳐 mid로 이동시킨다. // hanoi(n-1,start,to,mid)
- 가장 밑 원판을 to로 옮긴다.
- n-1개를 n단계 기준 mid에서 start를 거쳐 to로 이동시킨다. // hanoi(n-1,mid,start,to)

3. 베이스 조건 (가장 간단한 경우) 무엇을 리턴할지 생각한다.
n==1인 경우, 곧바로 원판을 start에서 to로 옮기면 된다. 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        hanoi(N, 1, 2, 3);
        System.out.println((int)Math.pow(2,N)-1);
        System.out.println(sb);
    }

    // n개를 start에서 mid를 거쳐 to로 옮기는 순서를 출력함
    public static void hanoi(int n, int start, int mid, int to){
        if(n==1){
            sb.append(start + " "+to+"\n");
            return;
        }

        hanoi(n-1,start, to, mid);
        sb.append(start + " "+to+"\n");
        hanoi(n-1,mid,start,to);
    }
}

재귀함수를 위 방법으로 하나하나 설계하다보니, 막힘없이 코드를 짤 수 있었다.

---

재귀함수로 알고리즘 문제를 풀 때 중요한 것

1. 어떤 재귀함수를 쓸 것인지 생각하기

큰 그림을 생각하고 / 이전 단계와의 조합을 고려하고 / 베이스 조건을 설정하고 ....
하면 재귀함수를 간단히 만들 수 있다.

하지만 무엇보다 중요한 것은 '문제를 풀 재귀함수 자체를 생각해낼 수 있는가?'이다.
하노이탑 문제도 재귀함수를 이용해서 푸는 것 같긴 한데, 어떤 재귀함수를 써야되는지 모르겠어서 막혔었다.

문제를 풀 재귀함수를 떠올리는 것에는 방법론이 없다고 생각이 된다.
여러 재귀함수 문제를 보고, 문제를 풀 때 그 단계를 나누는 연습을 하면 실력이 늘어날 것 같다.

2. 먼저 재귀함수를 설계하고 코딩 시작하기

특히 재귀함수 문제는 풀릴 듯 하면서 안풀리기 때문에 시간을 많이 잡아먹는다.
코드를 짜기 전에 '어떤 재귀함수를 어떻게 설계할 것인지'를 정하지 않으면
설계 자체가 잘못되었는지도 모른채로 콜스택 디버깅의 굴레에서 빠져나오지 못할 수도 있다. 
따라서 코드를 치기 전에 먼저 문제를 풀어야 한다. 
내가 풀 수 없는 문제를 컴퓨터에게 시킬 수는 없다.