백준1914번 하노이 탑(Hanoi tower) C++로 구현해보기

 

이번 글을 통해 배워갈 내용

1.  하노이 탑에 대한 정의
2.  하노이 탑을 C++로 구현 해보겠습니다.

---

 

 

하노이의 탑의 정의

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

하노이의 탑 - 위키백과, 우리 모두의 백과사전

 

위키피디아를 보시면 아시겠지만

A지점에 있는 원판들을 C 지점으로 옮기면 되는 간단한 문제입니다.

 

단 몇가지 조건이 있습니다.

조건1 : 크기가 작은 원판은 크기가 큰 원판의 위에 위치해야합니다.

조건2: 옮길수 있는 최소 경우의 수를 구해야합니다.

 

이해를 하셨다면 

 

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

1914번: 하노이 탑

백준문제를 한번 풀어보시고 30분 이내로 못푸신다면 아래 내용을 읽어주시면 됩니다.

 

---

 

첫번째 시도

 

저는 이 문제를 보고 처음에는 아래와 같이 시도하였습니다.

 

#include<iostream>

using namespace std;

int TOH(int n)
{
	if (n == 1)
	{
		return 1;
	}
	else
	{
		return TOH(n - 1) * 2 + 1;
	}
}

void main()
{
	cout << TOH(20) << endl;
	return;
}

간단하게 이야기하면

 

한개가 있을 경우 TOH(1) 이기 때문에 A->C로 한번 움직이면 됩니다.

 

두개가 있을 경우 TOH(1) 을 A->B 로 해주고 맨 아래 있는 원판을 C 로 한번 움직이고 다시 TOH(1)을 B->C로 해줍니다.

 

두개가 있을 경우 TOH(2) 을 A->B 로 해주고 맨 아래 있는 원판을 C 로 한번 움직이고 다시 TOH(2)을 B->C로 해줍니다.

 

그렇게 진행하면

 

Overflow 나는 지점까지는 계산이 가능하지만

 

값이 커질 경우

 

int 의 값을 넘어서면서 Overflow가 나기 때문에 -1이 나옵니다.

 

---

두번째 시도

 

 

#include<iostream>
using namespace std;

// 곱하기 2 더하기 1
string MulTwoAddOneFn(string str)
{
	int carry = 1;
	string tempStr = "";

	for (int i = (str.length() - 1); i >= 0; i--)
	{
		int mul = (str[i] - '0') * 2 + carry;
		tempStr.push_back(mul % 10 + '0');
		carry = mul / 10;
	}
	if (carry)
	{
		tempStr.push_back(carry + '0');
	}

	reverse(tempStr.begin(), tempStr.end());

	return tempStr;
}



string TOH(int n)
{
	if (n == 1)
	{
		return "1";
	}
	else
	{
		return MulTwoAddOneFn(TOH(n - 1));
	}
}

void main()
{
	cout << TOH(100) << endl;
	return;
}

 

TOH(100) =

1267650600228229401496703205375

도 잘 나옵니다.

 

백준 문제의 경우 20번째 타워 미만일때

스텝도 적어 줘야 하기 때문에 그부분도 작성해보겠습니다.

 

#include<iostream>
#include<algorithm>
using namespace std;

// 곱하기 2 더하기 1
string MulTwoAddOneFn(string str)
{
	int carry = 1;
	string tempStr = "";

	for (int i = (str.length() - 1); i >= 0; i--)
	{
		int mul = (str[i] - '0') * 2 + carry;
		tempStr.push_back(mul % 10 + '0');
		carry = mul / 10;
	}
	if (carry)
	{
		tempStr.push_back(carry + '0');
	}

	reverse(tempStr.begin(), tempStr.end());

	return tempStr;
}

string TOH(int n)
{
	if (n == 1)
	{
		return "1";
	}
	else
	{
		return MulTwoAddOneFn(TOH(n - 1));
	}
}

void TohShowSteps(int n, int from, int between, int to)
{
	if (n == 1)
	{
		cout << from << " " << to << endl;
	}
	else
	{
		TohShowSteps(n - 1, from, to, between);
		cout << from << " " << to << endl;
		TohShowSteps(n - 1, between, from, to);
	}

}

int main()
{
	int n = 0;

	cin >> n;

	cout << TOH(n) << endl;

	if (n <= 20)
	{
		TohShowSteps(n, 1, 2, 3);
	}
	return 0;
}

 

결과:

5

31

1 3

1 2

3 2

1 3

2 1

2 3

1 3

1 2

3 2

3 1

2 1

3 2

1 3

1 2

3 2

1 3

2 1

2 3

1 3

2 1

3 2

3 1

2 1

2 3

1 3

1 2

3 2

1 3

2 1

2 3

1 3

5 입력을 했을 때도 잘 나옵니다.

 

다만 아쉽게도 시간초과가 나옵니다

 

이는 입력 받는 방법이 cout 과 cin 이여서 출력 방법을 바꿔보겠습니다.

 

#include<iostream>
#include<algorithm>
using namespace std;

// 곱하기 2 더하기 1
string MulTwoAddOneFn(string str)
{
	int carry = 1;
	string tempStr = "";

	for (int i = (str.length() - 1); i >= 0; i--)
	{
		int mul = (str[i] - '0') * 2 + carry;
		tempStr.push_back(mul % 10 + '0');
		carry = mul / 10;
	}
	if (carry)
	{
		tempStr.push_back(carry + '0');
	}

	reverse(tempStr.begin(), tempStr.end());

	return tempStr;
}

string TOH(int n)
{
	if (n == 1)
	{
		return "1";
	}
	else
	{
		return MulTwoAddOneFn(TOH(n - 1));
	}
}


void TohShowSteps(int n, int from, int between, int to)
{
	if (n == 1)
	{
		printf("%d %d\n", from, to);
	}
	else
	{
		TohShowSteps(n - 1, from, to, between);
		printf("%d %d\n", from, to);
		TohShowSteps(n - 1, between, from, to);
	}

}

int main()
{
	int n = 0;

	cin >> n;

	cout << TOH(n) << endl;

	if (n <= 20)
	{
		TohShowSteps(n, 1, 2, 3);
	}
	return 0;
}

 

cout 을 printf로 바꿔주니

 

 

성공 메시지가 잘 나옵니다.

 

하노이의 탑은

 

정말 알고리즘 책의 정석적인 문제인 만큼

 

여러 좋은 개념들이 들어 있는것 같습니다.

 

많은 것을 얻어 가셨기를 바라며

 

저는 이만 ~

---

 

오늘도 즐거운 코딩하시길 바랍니다 ~ :)

 

참조 및 인용

https://stackoverflow.com/questions/6739362/towers-of-hanoi

Towers of Hanoi

C++ Primer