[C++] 백준 11729 하노이 탑 - 재귀

#pragma once
#include <iostream>
using namespace std;

void Hanoi(int n, int from, int to, int other);

int main()
{
	int i = 0;
	cin >> i;	//입력값

	//몇 번 이동하는지
	{
		int hanoiNum = 2;
		for (int y = 0; y < i - 1; y++)
			hanoiNum *= 2;
		cout << hanoiNum - 1 << "\n";
	}

	Hanoi(i, 1, 3, 2);

	return 0;
}

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

탑을 옮긴 총 횟수는 2의 n제곱 -1이다.

 

탑을 옮기는 과정은 이러하다.

 

1.  1번 기둥에 있는 가장 큰 원반을 3번 기둥으로 옮기기 위해 n-1개 원반을 2번 기둥에 옮긴다.
2.  1번 기둥에 가장 큰 원반을 3번 기둥으로 옮긴다.
3.  2번 기둥에 있는 n-1개 원반을 3번 기둥으로 옮긴다.

목표 설정

처음의 Hanoi(int n, int from, int to, int other) 함수는

n : 개수 n

from : 최초 시작 기둥 1

to : 최종 도착 기둥 3

other : 나머지 기둥 2

으로 변수를 받아준다.

 

1. 함수안에서는

n-1개를 보낼때에 1번 기둥에서 시작 하고 도착지는 2번 기둥이므로

Hanoi(n-1, from,      other,      to)를 넣어준다.

                        1           2           3

Hanoi(int n, int from, int to, int other)

결국 other 2번 기둥이 도착지 to가 된다.

 

2. n == 1일때 n만이 남았으므로 1번 기둥에서 3번기둥으로 보내준다.

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

                                1    3

 

3. 마지막으로 2번 기둥에 있는 n-1개 원반을 3번 기둥으로 옮긴다.

Hanoi(n-1, other,      to ,      from)

                        2          3           1

Hanoi(int n, int from, int to, int other)

 

---

최종 순서도

원반이 2개 일때

 

1번 기둥의 맨 위에 있는 원반 하나를 2번 기둥에 옮긴다. ( 1 -> 2 )

- Hanoi(n-1, from, other, to)로 들어간다.

- n이 1된다.

- 그렇게 n이 1이므로

Hanoi(n-1, from,      other,      to)

                        1           2           3

Hanoi(int n, int from, int to, int other)

 

printf("%d %d\n", from, to) from은 1, to는 2로 출력하여

1 2 출력

- if문을 들어갔기때문에 hanoi(n-1, from,      other,      to)함수 종료

---

1번 기둥의 마지막 남아있는 원반 하나를 3번 기둥에 옮긴다. ( 1 -> 3 )

- 빠져 나왔기 때문에 변수값 복귀  

Hanoi(int n, int from, int to, int other)

                             1           3           2

printf("%d %d\n", from, to) from은 1, to는 3로 출력하여

1 3 출력

 

---

2번 기둥에 있는 원반 하나를 3번 기둥에 옮긴다. ( 2 -> 3 )

- Hanoi(n - 1, other, to, from)로 들어간다.

- n이 1된다.

- 그렇게 n이 1이므로

Hanoi(n-1, other,      to,      from)

                        2           3           1

Hanoi(int n, int from, int to, int other)

 

printf("%d %d\n", from, to) from은 2, to는 3로 출력하여

2 3 출력

함수의 끝에 도달하여 함수 종료.

 

 

이것을 하면서 느낀점은 재귀를 하나씩 돌려가면서 하려니까 헷갈렸는데 어떻게 활용을 해야될지도 생각하기 어려웠다.

결국 원초적으로 간략하게 생각을 하고 함수를 만든 후 보니 다른 사람들의 코드와 비슷해졌다.