[재귀 함수] 하노이의 탑

하노이의 탑 (Tower of Hanoi)

세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고

퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여있다

출처 : 위키백과

아래 두 가지 조건을 만족시키며 탑 전체를 다른 기둥으로 옮겨 다시 쌓는 게임이다

1. 한 번에 한 개의 원판만 옮길 수 있다

2. 큰 원판이 작은 원판 위에 있어서는 안 된다

 

원리

알고리즘 강의를 들을때 분명 배웠던 내용이지만 (머리가 기억하지 못하니ㅠ_ㅠ ) 다시 공부를 했다

글만 보고는 원리를 한 번에 이해하기 힘들기 때문에 글을 읽은 다음 항상 영상을 찾아보곤 한다

재귀함수랑 하노이의 탑을 이해하기 위해 봤는데 도움이 많이 되었다

[출처:얄팍한 코딩사전] https://www.youtube.com/watch?v=aPYE0anPZqI 

출처 - 얄팍한 코딩사전

정리하자면

1. A B C 세 개의 탑이 있을 때 A에 원판 N개가 크기 순서대로 쌓여있다

2. A에서 C로 옮기기 위해서는 원판 N-1개를 B로 옮긴 후 나머지 가장 큰 원판 1개를 C로 옮긴다

3. 2번 과정에서 N-1개의 원판을 B로 옮기기 위해서는 N-2개 원판을 C로 미리 옮겨야 한다

...

이 과정이 똑같이 반복되기 때문에 재귀함수를 쓰는 것이다

 

수학적 규칙

우리가 구해야 하는 것은 A에 있는 N개의 원반을 C로 옮기는데 총 몇 번의 이동이 있었는지다

코드를 작성하기에 앞서 수학적 원리를 먼저 찾아보았다

n번째 원반을 한쪽 기둥으로 옮기는데 필요한 최소 횟수를 $a_{n}$ 이라고 하자 그렇다면

① n+1 번째 원반을 옮기기 위해서는 n번째까지의 원반을 한쪽 기둥으로 옮기고 → $a_{n}$

② n+1 번째 원반을 비어있는 기둥에 옮기고 → 1

③ n번째까지의 원반을 n+1번째 원반 위로 옮기면 된다 → $a_{n}$

결과적으로 $a_{n+1}$ = 2$a_{n}$ + 1 이 된다

여기서 양 변에 1씩 더해주고 $a_{n}$ + 1을 $b_{n}$으로 치환하면 

$b_{n+1}$ = 2$b_{n}$ 이 되는데, $b_{1}$ = $a_{1}$ + 1 = 2 이므로

$b_{n}$은 첫째항이 2이고 공비가 2인 등비수열이 된다

따라서 $b_{n}$ = $2^{n}$ = $a_{n}$ + 1 이고, 

$a_{n}$ = $2^{n}$ - 1이 된다

시간 복잡도는 O($2^{n}$)이다 굉장히 안좋다

 

하노이의 탑 코드

import java.util.Scanner;

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		sb.append((int)(Math.pow(2, n)-1)).append("\n");
		
		hanoi(n,1,2,3);
		System.out.println(sb);
	}

	public static void hanoi(int n, int start, int mid, int end) {
		if(n==1) {
			sb.append(start+" "+end+"\n");
			return;
		}

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

위에 수학적 규칙에서 말했듯이

재귀의 마지막에 n-1을 중간(mid)에 넣고,

가장 큰 원반 1개를 처음(start)에서 마지막(end)에 넣고,

중간(mid)에 있는 n-1개를 마지막(end) 위에 얹어주면 되는 과정이다

(코드는 여러 블로그를 참조하여 작성하였는데, 밑에 참조 링크를 걸어두었습니다)

 

실패 과정

처음에는 알고리즘은 이해했으나 코드로 구현하는 데 오래 걸렸다

막상 실행해도 머릿속에서 생각했던대로 실행되지 않았고, 결국 구글링을 통해 여러 블로그를 참조하였다

다른 사람들의 코드를 훑어보면서 방법을 자세하게 이해하고 다시 코드를 작성하였다

코딩 연습을 시작하면서 이런 문제가 있을 때는 항상 그때그때 나온 값들을 print해도 문제가 발생하지 않았다

그런데 시간 초과가 발생하여 참조하던 블로그를 다시 읽어보니까

자바의 경우 출력함수 print을 통해 매번 호출하면 시간 초과가 발생한다 적혀있었다

보니까 이런 경우에는 어차피 출력만 하면 되기 때문에 매번 출력해주는 것이 아니라 

StringBuilder 처럼 한 곳에 저장한 다음 마지막에 print를 한 번만 써서 출력해주는게 더 효율적인거같다

Scanner을 사용할 때는 StringBuilder 또는 StringWriter를 사용하는게 좋고

아니면 Scanner보다 더 효율적인 BufferedReader를 사용하는 것이 좋은 것 같다

 

Scanner ? BufferedReader ? StringBuilder ?

이런 것을 읽다보니 BufferedReader의 사용법은 익혔어도

BufferedReader가 정확하게 무엇인지, 왜 더 효율적인지 알고싶어졌다

이것도 분명 JAVA 강의 시간에 배웠지만.. 인간은 망각의 동물이다.. 

이번에는 확실하게 공부해본 다음에 포스팅해서 올려야겠다!

참조 : https://st-lab.tistory.com/96

문제 추천 [백준 11729] : https://www.acmicpc.net/problem/11729