[11729] 하노이 탑 이동 순서 - 재귀 ★★☆☆ / 복습 ●○

[ 문제 ] : https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

---

[ 문제 접근 ]

 

알고보니 유명한 재귀 문제인데 잘 몰랐다..

처음에는 stack을 사용해서 하려고 했는데 감이 안잡혀서 유튜브에 하노이 코딩을 검색해서 풀었다.

 

<21.12.01>

바킹독 알고리즘을 공부하면서 복습겸 다시 풀어봤는데 못풀었다.

그냥 재귀로 어떻게 풀어야될지 감조차 안왔다.

첫번째 문제풀때 제대로 이해하고 넘어가지 않았다는 의미이다.

반성 해야겠다.

 

 

 

---

[ 최종 코드 ]

#include<iostream>
#include<cmath>

using namespace std;
int n;

//int start = 0;
//int end = 2;

void move(int n,int s,int t) {
	int other = 6 - s - t;
	if (n == 1) {
		cout << s << " " << t << '\n';
	}
	else {
		move(n - 1, s, other);
		move(1, s, t);
		move(n - 1, other, t);
	}
}

int main() {
	std::cin >> n;
	cout << (1 << n) - 1 << '\n';
	move(n,1,3);
	return 0;
}

---

[ Key Point ]

 

👉 처음에 other을 전역 변수로 줬다가 낭패를 봤다. other은 매 단계마다 바뀌어야한다.

기둥의 합이 6인것을 이용해 s + t + other = 6    other을 구할 수 있다.

int other = 6 - s - t

 

👉 2^ n 제곱은   1 << n 이다.

 

---

[ 배운점 ]

 

 

재귀는 선언적 프로그래밍이다.

재귀는 디버깅으로 하나씩 들여다 보면 안된다.

재귀는 1. 종료조건 , 2. 문제의 정의만 잘 생각하자.

 

 

 

 

 

 

 

 

 

실제로 하노의 탑을 생각해보면,

 

 

 

 

 

- 종료 조건 : N==1 일때 옮기면 끝이다.

 

- N개의 원반을 옮기려면 N-1 개의 원발을 Other 기둥에 옮긴다.

- 가장 큰 원반을 최종 목적 기둥으로 옮긴다.

- 이웃한 기둥에서 N-1개의 원반을 목적 기둥으로 옮긴다.

 

 

이 세 가지를 가지고 코드를 짜면 된다.

 

---

[ 다른 사람 풀이 ]

 

ref : https://www.youtube.com/watch?v=uSSC0aKXbWQ&t=666s

ref : https://www.youtube.com/watch?v=AogMbfRwguk