[BaekJoon/C] No.11729 : 하노이 탑 이동 순서

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

 

No. 11729 문제

 

 

문제해석

 

재귀 알고리즘의 이용합니다.

 

1) 원판의 개수를 입력받습니다.

2) 원판을 이동시켜주는 함수를 작성하여 함수를 호출합니다.

 

 ex. 3개의 원판

1.  맨 위 원판 -> 3번 장대
2.  2번 원판 -> 2번 장대(중간 장대)
3. 1번 원판 -> 2번 장대(3번 장대는 아무것도 없는 상태)
4.  3번 원판 -> 3번 장대(1번 장대는 아무것도 없는 상태)
5.  1번 원판 -> 1번 장대
6.  2번 원판 -> 3번 장대
7.  1번 원판 -> 3번 장대

 

 

소스코드 & 문제풀이

 

#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); // n-1개의 원판을 첫 번째 장대에서 중간 지점 장대로 옮겨줍니다
		printf("%d %d\n", a, b); // 가장 큰 원판을 첫 번째 장대에서 마지막 장대로 옮깁니다
		hanoi(6 - a - b, b, n - 1); // 중간 장대에 있던 n-1개의 원판을 마지막 장대로 옮깁니다
	}
}

int main()
{
	int n; // 원판의 개수
	int t;
	scanf("%d", &n);
	t = pow(2, n) - 1; // 하노이의 탑에서 원판을 옮길 때 필요한 총 이동횟수를 계산합니다
	printf("%d\n", t);
	hanoi(1, 3, n); // 첫 번째 장대에서 세 번째 장대까지 n개의 원판을 옮기는 함수를 호출합니다
}

 

예제 입출력 결과

 

입력 : 3 / 출력 : 7...

 

 

*참고 

 

https://velog.io/@kimmainsain/C%EC%96%B8%EC%96%B4-%EB%B0%B1%EC%A4%80-11729-%ED%95%98%EB%85%B8%EC%9D%B4-%ED%83%91-%EC%9D%B4%EB%8F%99-%EC%88%9C%EC%84%9C

[C언어] 백준 11729 : 하노이 탑 이동 순서

 

https://codevang.tistory.com/73

백준알고리즘_11729_재귀함수_하노이탑 이동 (C언어)