n퀸을 풀기 위해 백트래킹을 연습하려고 했다. 그래서 유튜브에 백트래킹 강의를 찾아봤는데, 돌고돌아 재귀를 연습해야된다는 결론이 나왔다. 그렇게 하노이탑을 연습하게 되었다.
정리
https://blog.encrypted.gg/943 바킹독님 유튜브와 블로그에서 글을 정독했다.
먼저, 제일 중요한건 귀납적인 방식을 고려해야 된다는 것이다. 예를 들어, 첫번째 도미노를 쓰러뜨리면, 2번째, 3번째, 4번째... 마지막까지 쓰러진다.
우리는 일반적으로 하나씩 진행을 해왔다. 괄호가 있으면 스택이나 배열을 잘 해주었는지, 다음 차례때는 어떤걸 넣어야 하는지... 이런 마인드를 버리고 귀납적인 생각을 해야한다.
다시 도미노로 돌아와 1, 2, 3... 이 방식이 아니고 k번째 도미노가 쓰러졌다면, k + 1번째가 쓰러지며, 결국 마지막까지 쓰러진다. 이렇게 생각해야한다.
하노이의 탑도 같은 논리이다.
n개의 탑이 있다고 생각을 해보자. a, b, c의 기둥(장소)이 있다. a에 n개의 탑이 쌓여있고, c에 n개의 탑을 놓아야 한다.
그러면 b장소에 n-1을 놓고, c장소에 n을 놓는다. 그리고 나머지 b장소에 있는 n - 1의 탑을 c장소로 옮긴다. 끝이다.
코드
#include <stdio.h>
#include <math.h>
int hanoi(int a, int b, int n)
{
if (n == 1)
printf("%d %d\n", a, b);
else
{
hanoi(a, 6 - a - b, n - 1);
printf("%d %d\n", a, b);
hanoi(6 - a - b, b, n - 1);
}
}
int main()
{
int n;
int t;
scanf("%d", &n);
t = pow(2, n) - 1;
printf("%d\n", t);
hanoi(1, 3, n);
}https://codevang.tistory.com/73 여기에 자세한 내용이 적혀있다.
간단하게 생각한다면, n = 1일때, if에 걸리면서 1번장소와 3번장소 출력 후 종료
n = 2일때, n - 1개를 2번장소로 옮기고hanoi(a, 6 - a - b, n - 1);, n을 3번장소로 옮긴다. if (n == 1), 그리고 남은 n - 1개를 3번장소로 옮긴다.hanoi(6 - a - b, b, n - 1);
잘 이해가 안된다면, 위 티스토리를 들어가서 다시 봐보자.
https://www.youtube.com/watch?v=FYCGV6F1NuY&t=379s&ab_channel=%ED%8C%8C%EC%9D%B4%EC%8D%AC%ED%81%B4%EB%9E%98%EC%8A%A4
영상으로 정리가 정말 잘 되어있다.
