recursive_11729

문제 출처: https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

void hanoi(int N, int from, int by, int to){
	if(N==1){
		printf("%d %d", from, to);
	} else {
		hanoi(N-1, from, by, to);
		printf("%d %d", from, to);
		hanoi(N-1, to, from, by);	
    }
}

 

C++로 구현한 하노이 탑 알고리즘이다. 간단히 말로 설명하면 (N개의 원판이라 가정한다.)

 

(1) 가장 큰 원판을 3번 장대의 맨 아래에 두기 위해 그 위의 N-1개를 2번 장대로 옮겨준다.

(2) 가장 큰 원판을 3번 장대로 옮겨준다.

(3) 2번 장대의 모든 원판을 3번 장대로 옮겨준다.

 

 

 

코드를 통해서 하나씩 살펴보자.

 

void hanoi(int N, int from, int by, int to)

 

N은 원판의 개수이고, from(어디서), by(어디를 거쳐서), to(어디로) 갈 것인지 정보를 넘겨주는 매개변수이다.

 

if(N==1){
	printf("%d %d", from, to);
}

 

if(N==1) 이란 것은 원판의 갯수가 1일 때이다. 재귀 함수가 자신을 호출하다가 자신 위에 있는 원판이 한 개 일 때 from 에서 to로 자신 위의 원판을 옮겨주는 것이다.

 

else {
	hanoi(N-1, from, to, by);
	printf("%d %d", from, to);
	hanoi(N-1, by, from, to);
}

 

핵심 부분이다. 가장 이해하기 어려운 부분이므로 하나씩 살펴보자.

 

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

 

이 부분의 의미를 보면 N-1개를 from에서 by로 to를 거쳐서 옮기겠다는 뜻이다. 그 이유는 원판의 크기가 일정하지 않기 때문에, [1]번 부분의 맨 마지막에 있는 원판을 우선적으로 to([3]번)로 옮겨야 한다. 따라서 [1]번 부분 맨 아래의 원판을 제외하고 모두 [2]번 으로 옮겨야 한다. 함수 호출로 살펴보자.

                                                                   ([1],[2],[3]은 장대 번호를 의미한다. I, II, III은 원판 번호이다.)

 

hanoi(3, 1, 2, 3)을 메인에서 호출했을 경우

 hanoi(2, 1, 3, 2)가 재귀로 호출된다. 이것은 N==1이 아니므로 else 함수에서 다시 자신을 부른다.

  hanoi(1, 1, 2, 3)가 호출되면 N==1에서 true이므로 [1]의 맨 위의 판(I) 을 [1] ---> [3]으로 옮겨준다.

                          그 후 이 함수는 종료된다.

 hanoi(2, 1, 3, 2)에서 printf를 수행한다. 즉 [1]의 두번째 판(II)을 [2]로 옮긴다. 그후 재귀로 다시 한번

  hanoi(1, 3, 1, 2)가 호출된다. N==1에서 true이므로 [3]에 있던 첫번째 판(I)을 [2]로 옮긴다.

 

여기 까지 hanoi(N-1, from, to, by) 구문을 통해서 맨 아래 판(III)을 제외한 N-1개 판을 by [2]로 옮겨주게 된 것이다.

그 다음은 맨 아래 판을 [3]으로 옮겨주는 단계이다.

 

printf("%d %d", from, to)

 

hanoi(3, 1, 2, 3)에서 printf를 수행한다. 즉 [1]의 맨 아래 판(III)을 [1] ---> [3]으로 옮겨준다.

 

hanoi(N-1, by, from, to)

 

마지막으로 [2]에 있던 원판들을 [3]으로 옮겨주는 과정이다.

 

hanoi(3, 1, 2, 3)에서 위 구문을 수행한다.

 hanoi(2, 2, 1, 3)가 else 구문을 수행한다.

  hanoi(1, 2, 3, 1)가 호출된다. N==1에서 true이므로 [2]의 맨 위의 판(I)을 [2] ---> [1]으로 옮겨준다.

                          그 후 이 함수는 종료된다.

 hanoi(2, 2, 1, 3)이 printf를 수행한다. 즉 [2]의 두번째 판(II)을 [3]으로 옮긴다. 그후 재귀로 다시 한번

  hanoi(1, 1, 2, 3)가 호출된다. N==1이므로 true이므로 [1]에 있던 첫번째 판(I)을 [3]으로 옮긴다.