백준알고리즘풀이[11729] 히노이 탑 이동 순서

문제 사이트 : https://www.acmicpc.net/problem/11729

생각의 시퀀스 및 풀이

최근 알고리즘을 제대로 공부해야겠다는 생각에 일명 "종만북"이라 불리는 "프로그래밍 대회에서배우는 알고리즘 문제해결 전략"을 구입했다. 종만북은 나에게 너무 어려운 책이였다. 종만북에 실려있는 예제는 난이도가 상당하게 느껴졌고, 풀이를 보면 어떻게 이런 생각을 했을까? 하게 만드는 책이였다. 암튼 이 책을 200페이지까지 보고 쉬어가는 느낌으로 백준 알고리즘 [분할 정복]파트를 풀기로 했다. 난 이미 종만북 200페이지까지 봤으니 분할 정복에 대해선 어느정도 아는 상황이였다.

 

처음엔 감도 안잡혔다. 일단 히노이 탑을 옮기는 상상부터 했다. 첫 번째 장대를 세 번째 장대로 옮겨야 하니까... 판이 1개일때는 (1, 3) 한 번, 판이 두 개일때는 (1, 2),(1, 3),(2, 3) 세 번... 

그리고 계속 고민하다가 분할 정복을 생각했다. 아니, 문제를 보기도 전에 분할 정복을 어떻게 적용시켜야하는지 고민부터 했던거 같다. 아무튼 판 N개가 있으면, 상위 N-1개의 판을 두 번째 장대에 옮긴 후, 마지막 N번째 판을 세 번째 장대에 옮기고 다시 두 번째 장대에 있던 N-1개의 판들을 다시 N번째 판에 옮기면 어느 정도 분할 정복을 적용시켰다고 할 수 있었다. 여기서 h(n) = 2*h(n-1) + 1, h(1) = 1 공식을 얻었다.

 

그리고 N-1 판들을 옮기는 것에 대한 코드를 어떻게 작성하지? 고민하다가 N-1 판들을 그 판들이 있던 첫 번째 장대로부터(from) 두 번째 장대로 옮기고 (tmp, 코드에서는 B) N을 세 번째 장대로 옮기는 (from to to)것을 변수를 엮어서 생각해냈다. 이 아이디어는 노트에 끄적이면서 생긴 것이다. 노트에는 다음과 같이 끄적였다.

 

A(1 to 2)//N-1을 옮기는 행동

B(1 to 3)//마지막 판 하나를 옮기는 행동

C(2 to 3)//다시 N-1을 옮기는 행동

 

이 아이디어를 얻자마자 바로 코드로 옮기기 시작했다.

 

다만, 증명은 나에게 너무 어려웠기에 알고리즘 정당성을 증명할 시간은 없었다. 아이디어를 바로 코드에 옮겼다.

class Hanoi {
private:
	int N;
public:
	void inputN() {
		cin >> N;
	}
	void solution() {
		printf("%d\n",times(N));
		h(1, 3, 2, N);
	}
	int times(int n) {
		if (n == 1)return 1;
		return times(n - 1) * 2 + 1;
	}
	void h(int from, int to, int B,int n) {
		if (n == 1) {
			printf("%d %d\n", from, to);
			return;
		}
		h(from, B, to, n - 1);
		printf("%d %d\n", from, to);
		h(B, to, from, n - 1);
		return;
	}
};

처음엔 h(...)함수에 int B변수가 없었다. from과 to 그리고 판이 하나있을 때는 print(from, to)를 하기 위한 변수 n만 있었다. 아이디어를 코드로 옮길때 h(...);print(...);h(...);를 구현하려면 from, to 가 아닌 다른 변수를 도입시켜야했다. 처음에는 무식하게 if문으로 만들까 생각했지만 불현듯 '그냥 매개변수로 넘기면 중복되지 않는 값을 넘길수 있지 않을까?' 라는 생각이 들어 변수 int B를 추가했다.