설명 및 느낀점 ¶
박스놀이.. 왜이렇게 답이 많은거야..T.T
검증의 귀차니즘.ㅋ
이번엔 전역변수 안썼으나.. 안의 구조체 전달을 포인터 전달로 변환하면 속도 향상할 수 있음 ^^;
소스코드 ¶
~cpp #include <iostream> #include <vector> using namespace std; const char DEBUG_READ[] = "3\n1 2 2 2 1 2\n3 3 3 3 3 3\n3 2 1 1 1 1\n10\n1 5 10 3 6 5\n2 6 7 3 6 9\n5 7 3 2 1 9\n1 3 3 5 8 10\n6 6 2 2 4 4\n1 2 3 4 5 6\n10 9 8 7 6 5\n6 1 2 3 4 7\n1 2 3 3 2 1\n3 2 1 1 2 3\n0"; const int BOX_FACE_NUMBER = 6; const char FACE_NAME[BOX_FACE_NUMBER][7] = {"front", "back", "left", "right", "top", "bottom"}; const int FRONT = 0; const int BACK = 1; const int LEFT = 2; const int RIGHT = 3; const int TOP = 4; const int BOTTOM = 5; struct SMyBox { SMyBox(int front, int back, int left, int right, int top, int bottom) { color[FRONT] = front; color[BACK] = back; color[LEFT] = left; color[RIGHT] = right; color[TOP] = top; color[BOTTOM] = bottom; } int color[BOX_FACE_NUMBER]; }; struct SBoxBlock { SBoxBlock(int inputNumber, int inputTopFace) { number = inputNumber; topFace = inputTopFace; } int number; int topFace; }; const char* AddBox(const char* readData, vector<SMyBox*>& myBoxs) { int front, back, left, right, top, bottom; sscanf(readData, "%d %d %d %d %d %d", &front, &back, &left, &right, &top, &bottom); myBoxs.push_back(new SMyBox(front, back, left, right, top, bottom)); //printf("%2d %2d %2d %2d %2d %2d\n", front, back, left, right, top, bottom); return strchr(readData, '\n') + 1; } inline int GetOppositeFace(int faceNumber) { if (1 == faceNumber % 2) return faceNumber - 1; return faceNumber + 1; } void SuchNextBox(vector<SMyBox*>& myBoxs, int boxNumber, int lastColor, vector<SBoxBlock>& myBoxStack, vector<SBoxBlock>& bestHeight) { //// 박스가 가장 작은것까지 쌓였을때. //// if (0 > boxNumber) { if (myBoxStack.size() > bestHeight.size()) { bestHeight = myBoxStack; } return; } vector<int> suchFaceList; suchFaceList.reserve(BOX_FACE_NUMBER); //// 밑바닥의 면과 색상이 같은 면을 찾아낸다. //// if (0 == lastColor) { for (register int i = 0; i < BOX_FACE_NUMBER; ++i) suchFaceList.push_back(i); } else { for (register int i = 0; i < BOX_FACE_NUMBER; ++i) { if (lastColor == myBoxs[boxNumber]->color[i]) { suchFaceList.push_back(GetOppositeFace(i)); } } } //// 맞는 면이 없을때. //// if (0 == suchFaceList.size()) { if (myBoxStack.size() > bestHeight.size()) { bestHeight = myBoxStack; } return; } //// 다른 상자를 올려봅니다. //// for (register int i = 0; i < (int)suchFaceList.size(); ++i) { myBoxStack.push_back(SBoxBlock(boxNumber, suchFaceList[i])); for (register int j = boxNumber - 1; j >= -1 ; --j) { SuchNextBox(myBoxs, j, myBoxs[boxNumber]->color[suchFaceList[i]], myBoxStack, bestHeight); } myBoxStack.pop_back(); } } void ShowBoxStack(vector<SBoxBlock>& showStack) { cout << showStack.size() << endl; for (register int i = (int)showStack.size() - 1; i >= 0 ; --i) { cout << showStack[i].number + 1 << " "; cout << FACE_NAME[showStack[i].topFace] << endl; } } void FreeMemory(vector<SMyBox*>& myBoxs) { for (register int i = 0; i < (int)myBoxs.size(); ++i) { delete myBoxs[i]; } } void main() { int boxNumber = 0; const char* readData = DEBUG_READ; for (int caseNumber = 1; ; ++caseNumber) { sscanf(readData, "%d", &boxNumber); readData = strchr(readData, '\n') + 1; if (0 == boxNumber) //예쁜 상자가 없으면 종료한다 -ㅡV break; vector<SMyBox*> myBoxs; for (register int i = 0; i < boxNumber; ++i) { readData = AddBox(readData, myBoxs); } vector<SBoxBlock> myBoxStack; vector<SBoxBlock> bestStack; SuchNextBox(myBoxs, (int)myBoxs.size() - 1, 0, myBoxStack, bestStack); cout << "Case #" << caseNumber << endl; ShowBoxStack(bestStack); FreeMemory(myBoxs); cout << endl; } }