순환-하노이탑 문제

하노이탑 문제

- 막대 A, B, C가 주어졌을 때 막대 A에 쌓여 있는 원판 3개를 막대 C로 옮기되 아래 조건들을 만족해야 함

• 한 번의 하나의 원판만 이동
• 맨 위에 있는 원판만 이동
• 크기가 작은 원판 위에 큰 원판을 쌓을 수 없음
• 중간의 막대 B를 사용할 수 있으나 앞의 조건들을 지켜야 함

- 막대의 개수가 많아질수록 문제가 복잡해짐

→ 순환을 이용하여 문제 해결(순환이 일어날수록 문제의 크기(=옮겨야 하는 디스크의 개수)가 작아짐)

 

n개의 원판이 A에 쌓여 있는 경우

1. 위에 쌓여 있는 n-1개의 원판을 B로 이동

2. 제일 밑에 있는 원판을 C로 이동

3. B에 있던 n-1개의 원판을 C로 이동

void hanoiTower(int n, char A, char B, char C) {
	//A에 쌓여있는 n개의 원판을 B를 사용하여 C로 이동
	
	if (n == 1) {
		//A에 있는 1개의 원판을 C로 이동
    }
	else {
		/*
		1. A의 최하단 원판을 제외한 나머지 원판들을 B로 이동
		2. A에 있는 남은 하나의 원판을 C로 이동
		3. B의 원판들을 C로 이동
		*/
	}
}

이때 else문 내의 문제는 기존 문제의 축소된 형태

- 1은 C를 사용하여 A에서 B로 n-1개의 원판을 이동하는 문제

- 3은 A를 사용하여 B에서 C로 n-1개의 원판을 이동하는 문제

→ 순환 호출 사용 가능

void hanoiTower(int n, char A, char B, char C) {
	//A에 쌓여있는 n개의 원판을 B를 사용하여 C로 이동
	
	if (n == 1)
		;//A에 있는 1개의 원판을 C로 이동
	else {
		hanoiTower(n - 1, A, C, B);
		//A에 있는 남은 하나의 원판을 C로 이동
		hanoiTower(n - 1, B, A, C);
	}
}