이번 문제는 명령셋을 일괄적으로 입력받은 다음, 입력이 끝날 때 최종상태를 출력하는 것이 목표입니다.
처음에는 블럭의 총 개수를 입력받고 그 이후에는 명령셋을 입력받습니다.
( 명령셋의 입력은 "quit" 명령이 나올때까지 반복합니다. )
인식가능한 명령셋은 다음과 같습니다.
move a onto b
a 블럭과 b 블럭 위에 다른 블럭이 있다면 해당 블럭들을 원래 위치로 복귀시킨 다음,
a 블럭을 b 블럭위로 옮긴다.
ex) a 위에 b 가 있고, c 위에 d 가 있을 경우, 'move c onto a' 라는 명령이 입력되면,
a 와 c 위의 b, d 를 원래 위치로 옮기고, c 를 a 위로 옮긴다.
move a over b
a 블럭 위에 다른 블럭이 있으면 해당 블럭들을 원래 위치로 복귀시키고,
a 블럭을 b 블럭이 있는 블럭 기둥의 맨 위로 옮긴다.
ex) a 위에 b, c 가 있을 경우 'move d over a' 라는 명령이 입력되면, d 는 c 위로 이동하게 됨.
pile a onto b
b 블럭 위에 다른 블럭이 있으면 해당 블럭들을 원래 위치로 복귀시키고,
a 블럭을 포함하여 a 블럭 위에 있는 모든 블럭을 b 블럭 위로 옮긴다.
이 때, 블럭이 쌓인 순서는 유지되어야 한다.
ex) a 위에 b, c 가 있고, d 위에 e 가 있을 경우, 'move a onto d' 라는 명령이 입력되면,
d 위의 e 는 제자리로 옮기고, a 를 포함해 a, b, c 를 쌓인 순서대로 d 위로 옮긴다.
pile a over b
a 블럭을 포함하여 a 블럭 위에 있는 모든 블럭을 b 블럭이 있는 블럭 기둥의 맨 위로 옮긴다.
ex) a 위에 b, c 가 있고, d 위에 e, f 가 있을 경우, 'move a over d' 라는 명령이 입력되면,
a 를 포함해 a, b, c 를 쌓인 순서대로 f 위로 옮긴다.
quit
입력을 끝내고, 블럭들의 최종 상태를 출력한다.
※ 주의사항
1. 같은 블럭에 대한 명령은 무시한다.
ex) move a over a, move d onto d
2. 같은 블럭 기둥에 있는 블럭들에 대한 명령은 무시한다.
ex) (a, b, c 가 같은 기둥일 때...) pile c over a, move b onto c
3. 그 외의 잘못된 입력은 무시한다.
다음은 'Accept' 받은 소스코드입니다.
1 //
2 // 101 - The Blocks Problem
3 //
4
5 #include <iostream>
6 #include <string>
7 #include <vector>
8 #include <stack>
9
10 using namespace std;
11
12 typedef struct _BlockField {
13 vector<int> vecBlocks;
14 } BlockField, *p_BlockField;
15
16 int main(void)
17 {
18 int nBlocks = 0;
19 int nSrcBlock = 0, nDstBlock = 0;
20 int *pBlockPos = NULL;
21 string strCommand1, strCommand2;
22
23 while (cin >> nBlocks) {
24 BlockField *pField = new BlockField[nBlocks];
25 pBlockPos = new int[nBlocks];
26
27 for (int i = 0; i < nBlocks; i++) {
28 pField[i].vecBlocks.push_back(i);
29 pBlockPos[i] = i;
30 }
31
32 while (cin >> strCommand1) {
33 if (strCommand1.compare("quit") == 0) break;
34
35 cin >> nSrcBlock >> strCommand2 >> nDstBlock;
36
37 if ((nSrcBlock >= nBlocks) || (nSrcBlock < 0) ||
38 (nDstBlock >= nBlocks) || (nDstBlock < 0)) continue;
39 if ((nSrcBlock == nDstBlock) || (pBlockPos[nSrcBlock] == pBlockPos[nDstBlock])) continue;
40
41 int nTemp = 0;
42
43 if (strCommand1.compare("move") == 0) {
44 if (strCommand2.compare("onto") == 0) {
45 // nSrcBlock 위의 블럭들 원래 위치로~
46 while (pField[pBlockPos[nSrcBlock]].vecBlocks[pField[pBlockPos[nSrcBlock]].vecBlocks.size()-1]
47 != nSrcBlock) {
48 nTemp = pField[pBlockPos[nSrcBlock]].vecBlocks[pField[pBlockPos[nSrcBlock]].vecBlocks.size()-1];
49 pField[nTemp].vecBlocks.push_back(nTemp);
50 pBlockPos[nTemp] = nTemp;
51 pField[pBlockPos[nSrcBlock]].vecBlocks.pop_back();
52 }
53
54 // nDstBlock 위의 블럭들 원래 위치로~
55 while (pField[pBlockPos[nDstBlock]].vecBlocks[pField[pBlockPos[nDstBlock]].vecBlocks.size()-1]
56 != nDstBlock) {
57 nTemp = pField[pBlockPos[nDstBlock]].vecBlocks[pField[pBlockPos[nDstBlock]].vecBlocks.size()-1];
58 pField[nTemp].vecBlocks.push_back(nTemp);
59 pBlockPos[nTemp] = nTemp;
60 pField[pBlockPos[nDstBlock]].vecBlocks.pop_back();
61 }
62
63 // nSrcBlock 을 nDstBlock 위로~
64 pField[pBlockPos[nDstBlock]].vecBlocks.push_back(nSrcBlock);
65 pField[pBlockPos[nSrcBlock]].vecBlocks.pop_back();
66 pBlockPos[nSrcBlock] = pBlockPos[nDstBlock];
67 }
68 if (strCommand2.compare("over") == 0) {
69 // nSrcBlock 위의 블럭들 원래 위치로~
70 while (pField[pBlockPos[nSrcBlock]].vecBlocks[pField[pBlockPos[nSrcBlock]].vecBlocks.size()-1]
71 != nSrcBlock) {
72 nTemp = pField[pBlockPos[nSrcBlock]].vecBlocks[pField[pBlockPos[nSrcBlock]].vecBlocks.size()-1];
73 pField[nTemp].vecBlocks.push_back(nTemp);
74 pBlockPos[nTemp] = nTemp;
75 pField[pBlockPos[nSrcBlock]].vecBlocks.pop_back();
76 }
77
78 // nSrcBlock 을 nDstBlock 위로~
79 pField[pBlockPos[nDstBlock]].vecBlocks.push_back(nSrcBlock);
80 pField[pBlockPos[nSrcBlock]].vecBlocks.pop_back();
81 pBlockPos[nSrcBlock] = pBlockPos[nDstBlock];
82 }
83 }
84 else if (strCommand1.compare("pile") == 0) {
85 stack<int> pileBlocks;
86
87 if (strCommand2.compare("onto") == 0) {
88 // nDstBlock 위의 블럭들 원래 위치로~
89 while (pField[pBlockPos[nDstBlock]].vecBlocks[pField[pBlockPos[nDstBlock]].vecBlocks.size()-1]
90 != nDstBlock) {
91 nTemp = pField[pBlockPos[nDstBlock]].vecBlocks[pField[pBlockPos[nDstBlock]].vecBlocks.size()-1];
92 pField[nTemp].vecBlocks.push_back(nTemp);
93 pBlockPos[nTemp] = nTemp;
94 pField[pBlockPos[nDstBlock]].vecBlocks.pop_back();
95 }
96
97 // nSrcBlock 을 포함해서 스택에 저장
98 while (pField[pBlockPos[nSrcBlock]].vecBlocks[pField[pBlockPos[nSrcBlock]].vecBlocks.size()-1]
99 != nSrcBlock) {
100 nTemp = pField[pBlockPos[nSrcBlock]].vecBlocks[pField[pBlockPos[nSrcBlock]].vecBlocks.size()-1];
101 pileBlocks.push(nTemp);
102 pField[pBlockPos[nSrcBlock]].vecBlocks.pop_back();
103 }
104
105 if (pField[pBlockPos[nSrcBlock]].vecBlocks[pField[pBlockPos[nSrcBlock]].vecBlocks.size()-1]
106 == nSrcBlock) {
107 nTemp = pField[pBlockPos[nSrcBlock]].vecBlocks[pField[pBlockPos[nSrcBlock]].vecBlocks.size()-1];
108 pileBlocks.push(nTemp);
109 pField[pBlockPos[nSrcBlock]].vecBlocks.pop_back();
110 }
111
112 // nDstBlock 위로 이동
113 while (!pileBlocks.empty()) {
114 nTemp = pileBlocks.top();
115 pField[pBlockPos[nDstBlock]].vecBlocks.push_back(nTemp);
116 pBlockPos[nTemp] = pBlockPos[nDstBlock];
117 pileBlocks.pop();
118 }
119 }
120 if (strCommand2.compare("over") == 0) {
121 // nSrcBlock 을 포함해서 스택에 저장
122 while (pField[pBlockPos[nSrcBlock]].vecBlocks[pField[pBlockPos[nSrcBlock]].vecBlocks.size()-1]
123 != nSrcBlock) {
124 nTemp = pField[pBlockPos[nSrcBlock]].vecBlocks[pField[pBlockPos[nSrcBlock]].vecBlocks.size()-1];
125 pileBlocks.push(nTemp);
126 pField[pBlockPos[nSrcBlock]].vecBlocks.pop_back();
127 }
128
129 if (pField[pBlockPos[nSrcBlock]].vecBlocks[pField[pBlockPos[nSrcBlock]].vecBlocks.size()-1]
130 == nSrcBlock) {
131 nTemp = pField[pBlockPos[nSrcBlock]].vecBlocks[pField[pBlockPos[nSrcBlock]].vecBlocks.size()-1];
132 pileBlocks.push(nTemp);
133 pField[pBlockPos[nSrcBlock]].vecBlocks.pop_back();
134 }
135
136 // nDstBlock 위로 이동
137 while (!pileBlocks.empty()) {
138 nTemp = pileBlocks.top();
139 pField[pBlockPos[nDstBlock]].vecBlocks.push_back(nTemp);
140 pBlockPos[nTemp] = pBlockPos[nDstBlock];
141 pileBlocks.pop();
142 }
143 }
144 }
145 else continue;
146 }
147
148 for (int i = 0; i < nBlocks; i++) {
149 if (pField[i].vecBlocks.size() == 0) cout << i << ":";
150 else cout << i << ": ";
151
152 for (int j = 0; j < pField[i].vecBlocks.size(); j++) {
153 if (j == pField[i].vecBlocks.size()-1) cout << pField[i].vecBlocks[j];
154 else cout << pField[i].vecBlocks[j] << " ";
155 }
156 cout << endl;
157 }
158
159 if (pField != NULL) delete [] pField;
160 if (pBlockPos != NULL) delete [] pBlockPos;
161 }
162
163 return 0;
164 }
블럭 수에 따라 메모리를 동적으로 할당 한답시고 한 점이랑... 함수 호출의 오버헤드를 줄이려고...
한방에 다 작성을 하다보니 코드가 많이 복잡해졌습니다..;;
요런걸~ '나쁜 코드' 예로 들면 딱일텐데 말입니다... 아.하.하.하... ^^;;;;
( 요런데서.. 개발 표현력이 떨어지는구나.. 하며 반성을 많이 하게 됩니다..;;;; )
겹치는 부분을 함수화하고 접근방식을 달리하면 훨씬 보기 쉽고 깔끔한 코드가 나올 듯 하지만..
'Accept' 받고 난 이후로는 뭔가 의욕이 떨어져 버렸네요..;; ^^;;;..
101_The_Blocks_Problem.pdf
