[C] 백준 11729 : 하노이 탑 이동 순서

 

 

1. 문제

 

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

 

 

---

 

 

2. 접근

 

하노이 탑은 기둥 1에서 기둥 3까지 원반을 크기 순으로 옮기는 것이다.

 

 

게임의 조건은 다음과 같다.

1. 한 번에 한개의 원판만 옮길 수 있다.
2. 가장 위에 있는 원판만 이동할 수 있다.
3. 큰 원판이 작은 원판 위에 있어서는 안 된다.

 

먼저, 

n = 1인 경우 : 무조건 가능
n < k 인 경우 : 가능하다고 가정
n = k인 경우 : 가장 큰 것을 제외하고 k-1개를 기둥 2로 옮긴다. 그 다음, 가장 큰 원반을 기둥 1에서 3으로 옮긴다.
                       그 다음 기둥 2에 옮겨 놓은 k-1개를 기둥 3으로 옮긴다.

(n : 원반 개수, k : 임의의 기둥의 원반 개수)

위의 아이디어를 떠올릴 수 있다.

 

 

아이디어를 바탕으로 함수를 작성했다.

void moves(int n, char start, char dest, char tmp) {
	if (n == 1) printf("%d %d\n", start, dest);
	else {
		moves(n - 1, start, tmp, dest);
		printf("%d %d\n", start, dest); // 현위치
		moves(n - 1, tmp, dest, start);
	}
}

원반의 개수가 1인 경우, start에서 dest까지 한번에 이동할 수 있다.

원반의 개수가 1보다 큰 경우, (원반의 개수 - 1)개를 start에서 tmp로 이동한다.

그 다음 (원반의 개수 - 1)개의 원반을 다시 dest로 이동시킨다.

 

따라서,

T(n) : n개의 원반을 기둥 1에서 3으로 옮길 때 필요한 움직임의 횟수

• T(1) = 1
• T(n) = T(n-1)+1+T(n-1) = 2T(n-1)+1 (n>1)

👉 T(n) = 2^n - 1

 

 

---

 

 

3. 문제풀이

 

 

#include <stdio.h>
#include <math.h>

void moves(int n, char start, char dest, char tmp) {
	if (n == 1) printf("%d %d\n", start, dest);
	else {
		moves(n - 1, start, tmp, dest);
		printf("%d %d\n", start, dest);
		moves(n - 1, tmp, dest, start);
	}
}


int main(void) {
	int n, cnt;
	scanf_s("%d", &n);
	cnt = pow(2, n) - 1;
	printf("%d\n", cnt);
	moves(n, 1, 3, 2);
}

 

 

---

 

참고

 

 

https://codevang.tistory.com/73

https://ko.wikipedia.org/wiki/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98_%ED%83%91