2017. 5. 20. 13:28
프로그래밍
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 | /* 하노이 타워 [2017-03-28] */ /* 최적화가 필요합니다. */ #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <Windows.h> #define STACK_SIZE 100 template <typename T> class Stack { public: Stack() { memset(elementArr, 0, sizeof(T) * STACK_SIZE); m_size = 0; } void push(T elem) { if (m_size >= STACK_SIZE) { fprintf(stderr, "스택 - 용량이 부족합니다.\n"); exit(-1); } elementArr[m_size++] = elem; } T pop() { if (m_size <= 0) { fprintf(stderr, "스택 - 비어있습니다.\n"); exit(-1); } return elementArr[--m_size]; } T elementAt(size_t index) { if (index < 0 || index >= m_size) { fprintf(stderr, "스택 - 인덱스가 잘못되었습니다.\n"); exit(-1); } return elementArr[index]; } T top() { return elementAt(m_size - 1); } size_t size() { return m_size; } bool empty() { return (m_size <= 0) ? true : false; } private: T elementArr[STACK_SIZE]; size_t m_size; }; class Relation { public: Relation() { } Relation(Stack<int> *self, Stack<int> *target, Stack<int> *other) { m_self = self, m_target = target, m_other = other; } Stack<int> *m_self, *m_target, *m_other; }; void render(Relation relation, Stack<int> *aTower, Stack<int> *bTower, Stack<int> *cTower) { char selfTower, targetTower; if (relation.m_self == aTower) selfTower = 'a'; else if (relation.m_self == bTower) selfTower = 'b'; else selfTower = 'c'; if (relation.m_target == aTower) targetTower = 'a'; else if (relation.m_target == bTower) targetTower = 'b'; else targetTower = 'c'; printf("%d원판이 %cTower에서 %cTower로 이동되었습니다.\n", relation.m_target->top(), selfTower, targetTower); } int main() { Stack<int> aTower, bTower, cTower; Stack<int> *self, *target, *other; Stack<Relation> commandStack; Relation relation(&aTower, &cTower, &bTower); int self_top, target_size; int i, j, size; // 원판 설정 printf("Size : "); scanf("%d", &size); for (i = size; i >= 1; i--) aTower.push(i*2 - 1); // 현재 타워에서 목적 타워로 모든 원판을 옮길 것을 예약 size = relation.m_self->size(); for (i = 0; i < size; i++) commandStack.push(relation); // 예약된 모든 명령어를 실행 while (!commandStack.empty()) { relation = commandStack.pop(); self = relation.m_self, target = relation.m_target, other = relation.m_other; // 옮길 수 있는 경우 if (target->empty() || self->top() < target->top()) { target->push(self->pop()); render(relation, &aTower, &bTower, &cTower); // getchar(); } // 현재 원판보다 더 작은 원판이 있는 경우 else { self_top = self->top(); target_size = target->size(); // 작은 원판이 어디까지 있는지 탐색 (중간값을 확인하는 식으로 초기화 가능) for (i = target_size - 1; i >= 0 && self_top > target->elementAt(i); i--); // 작은 원판이 되돌아 올 것을 예약 for (j = i + 1; j < target_size; j++) commandStack.push(Relation(other, target, self)); // 현재 원판을 옮길 것을 예약 commandStack.push(Relation(self, target, other)); // 작은 원판을 다른 곳으로 옮길 것을 예약 for (j = i + 1; j < target_size; j++) commandStack.push(Relation(target, other, self)); } } // 출력 int num; for (i = cTower.size() - 1; i >= 0; i--) { num = cTower.elementAt(i); for (j = 0; j < num; j++) printf("*"); printf("\n"); } } | cs |
이 문제의 목적은 A 타워에 있는 N층의 원판을 C 타워로 옮기는 것입니다.
A 타워에 있는 3층의 원판을 C 타워로 옮길 경우 처음 상황은 다음과 같습니다.
* - -
*** --- ---
***** ----- -----
A B C
A 타워의 최하위 층을 옮길 경우 다음과 같은 상황이 됩니다.
- - -
--- -*- ---
----- -***- *****
A B C
그럼 이 상황은 다시 B에 있는 2층의 원판을 C 타워로 옮기는 문제로 생각할 수 있습니다.
이렇게 최하위에 존재하는 판을 옮기는 것을 기준으로 생각하면 DP 방법으로 풀 수 있습니다.
반복문으로 짜보고자 스택을 사용했지만, 사실 재귀 함수로 프로그래밍 한 것과 같습니다.
'프로그래밍' 카테고리의 다른 글
| 유튜브 뮤직 컨트롤러 (0) | 2020.09.07 |
|---|---|
| [개인 공부] 거북이 프로그램 (2) | 2017.06.07 |