-
코테 일기(8) : 하노이탑(The tower of Hanoi)프로그래밍/C++ 2020. 4. 20. 14:02반응형
하노이탑은 Divide and Conquer(정복 분할 기법)에서 가장 많이 다뤄지는 문제 중 하나다.
A에서 B를 거쳐 C로 옮기기 위해 하노이 탑의 순서는 다음과 같다.
1. (1,2)를 B로 옮긴다.
2. (3)을 C로 옮긴다.
3. (1,2)를 C로 옮긴다.
이를 코드로 그대로 옮기면 다음과 같다.
Code
//하노이탑 만들기
#include <iostream>
using namespace std;
int hanoi(int a, int b, int c, int d);
int main() {
int N;
cout << "탑의 개수를 선택하세요" << endl;
cin >> N;
cout << hanoi(N, 1, 2, 3) << endl;
}
int hanoi(int N, int a, int b, int c) {
int at = 0;
if (N == 1) {
cout << a << " " << c << endl; //N이 1이면 C로 옮긴다.
return 1;
}
at+=hanoi(N - 1, a, c, b);//자신을 제외한 N-1의 탑을 나머지 칸으로 옮긴다. (1번)
cout << a << " " << c << endl; //맨 밑의 탑을 C로 옮긴다. (2번)
at++; //hanoi 실행 횟수마다 1을 증가
at+=hanoi(N - 1, b, a, c); //나머지 칸에 있던 N-1의 탑을 C로 옮긴다. (3번)
return at;
}
Divide & Conquer를 쓰면 재귀 함수를 통해 간단하게 실행 할 수 있다.
중간 과정을 우리가 생각하지 않고 컴퓨터에게 맡기는 것이다.
과정을 컴퓨터에게 맡긴다는 것이 와닿지 않아 하드코딩을 하려했지만,
결국 이 문제는 정복 분할로만 풀어야 한다는 것을 깨달았다.
결과
전체 코드가 필요하신 분은 댓글로 이메일을 남겨주세요.
* 엄연히 제가 직접 작성한 코드입니다. 무단 복제는 금지해주세요!
'프로그래밍 > C++' 카테고리의 다른 글
코테 일기(10) : 백준 [1051번] 숫자 정사각형 (0) 2020.04.21 코테 일기(9) : 백준 [2178번] 미로찾기(BFS) (0) 2020.04.21 코테 일기(7) : 백준 [1260번] DFS와 BFS(DFS & BFS 완성) (0) 2020.04.20 코테 일기(6) : 백준 [1260번] DFS와 BFS(BFS편) (0) 2020.04.05 코테 일기(5) : CodeUp [1093] 이상한 출석 번호 부르기1 (0) 2020.04.05