재귀호출(재귀함수)-하노이 탑(백준1914번)

재귀를 이용한 하노이탑(백준1914번문제)

---

---

재귀를 이용한 하노이탑 문제풀이

---

package recursiveandbacktracking;
 
import java.math.BigInteger;
import java.util.Scanner;
 
public class Baekjun1914hanoiRecursive {
    static void hanoi(int N,char from,char aux,char to) {
        if(N==1) {
            System.out.println(from+" "+to);
        }else {
            hanoi(N-1,from,to,aux);
            System.out.println(from+" "+to);
            hanoi(N-1,aux,from,to);
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        BigInteger result=new BigInteger("1");
        if(N==1) System.out.println(1);
        else {
            for(int i=0;i<N;i++) {
                result=result.multiply(new BigInteger("2"));
            }
            result=result.subtract(new BigInteger("1"));
            System.out.println(result);
        }
        if(N<=20) {
            hanoi(N,'1','2','3');
        }
    }
 
}
 

여기서 문제는 N값이 20 이하 일때만 원반을 옮기는 과정을 출력하지만 20보다 클 경우에는 원반의 옮긴 수만 출력하면 된다. 여기서 옮긴 횟수를 함수 안에서 재귀호출 할때마다 카운트를 1씩 증가시키는 것으로 코드를 짜게되면 아마 시간 초과가 발생할 것이다.  왜냐면 조건에서의 가장 큰수 100을 입력하면 1267650600228229401496703205375라는 원반을 옮긴 횟수가 나오는데 보통 1억번에 1초정도 걸리는데 이것은 어마어마한 시간이 걸릴 것이므로 횟수는 카운트를 1씩 증가시키는 것이 아니라 점화식을 이용하여 횟수를 구한다.

즉, 원반을 옮기는 횟수는 2^N-1번이다.  N값이 100이라 가정했을 때는, 이 값은 long 데이터 타입도 수용하지 못할 값이므로 자바의 BigInteger 클래스를 이용해 횟수를 저장한다. 내부적으로 String을 가지므로 무한히 큰 값도 수용이 가능하다.

원반을 옮기는 과정의 함수를 설명하자면 예를들어 3개의 원반을 1번탑에서 3번탑으로 옮긴다면 hanoi(3,'1','2','3') 함수를 호출하게 된다. 그러면 함수 내부에서 재귀호출을 통해서 문제를 쪼개는 과정에 들어간다. 3개의 원반을 1번탑에서 3번탑으로 옮기는 것이라면 우선 더 작은 문제로 1번,2번 원반을 2번탑으로 옮긴후에 그다음 3번원반을 3번탑에 옮기고 그리고 1번,2번의 원반을 다시 2번탑에서 3번탑으로 옮기는 것 이렇게 문제를 작은 단위로 쪼개는 것이다. 이것이 총 3번의 과정으로 1번 n-1개의 원반을 보조탑(2번탑으로 옮기는과정)으로 옮기는 과정은 hanoi(2,from,to,aux) 함수에서 해결하고 그다음 3번원반을 1번탑에서 3번탑으로 옮기는 과정은 system.out.println(from+" "+to); 라는 출력문으로 그리고 마지막으로 보조탑에 있던 1번,2번 원반을 3번탑으로 옮기는 과정은 hanoi(2,aux,from,to) 함수에서 해결하게 된다. 그리고 각 함수 내에서 문제를 더 작은 단위로 쪼개고 쪼갠다. 예를 들어 1,2번 원반을 보조탑으로 옮기는 hanoi(2,from,to,aux) 함수에서 다시 문제를 1번원반을 보조탑인 3번탑으로 옮기는 과정(hanoi(1,1,2,3)과 2번원반을 2번탑으로 옮기는 과정(system.out.println(from+" "+to) 그리고 마지막으로 보조탑에 있던 1번원반을 목적탑인 2번탑으로 옮기는과정(hanoi(1,3,1,2))으로 마무리 되는 것이다. 

즉,

 hanoi(N-1,from,to,aux);

System.out.println(from+" "+to);

hanoi(N-1,aux,from,to);

이 과정이 n의 수가 1이 될때까지 계속 각 n값에 대하여 반복하게 되는 것이다.