C++ 핀볼 과제풀이 도움요청합니다..ㅜㅜ

Question

안녕하세요.. 제 과제는 아니고, 도와주려고 하는데 방법이 떠오르질 않아서 질문글 남깁니다.. 5 2 4 3 1 5이런형태로 핀볼이 있을때 나올수 있는 경우의수는523 521 541 545 총 4가지이고, 이 중 가장 큰 값은 5+4+5 = 14 에요.당연하게도 핀볼은 n줄에 값은 임의로 주어집니다..문제는.. 사용할 수 있는 조건이 한정적이에요.new 사용금지재귀함수 사용금지구현 가능한건 오로지 클래스 내 메소드 한개뿐입니다..샘플 소스 첨부합니다..고수님들.. 도움주세요.. ㅜㅜ===================================#include #include using namespace std;class ABC12 {public: int getMaxPoints(vector> &maze);};// ------------------------------------------------------------// DO NOT MODIFY ABOVE THIS LINE. The above is your C++ class // named ABC12 with a method called getMaxPoints(...) you will// implement// ------------------------------------------------------------int ABC12::getMaxPoints(vector> &maze) { return 0;}int main(){ // Instantiate an instance of the ABC12 class ABC12 abc12; // Your target method will be tested as such, with random input // as the following example illustrates vector> maze = { {0}, {4,1}, {5,3,8}, {1,6,7,3} }; cout << abc12.getMaxPoints(maze) << endl; // 16 return 0;}

songline · Answer

재귀 없이 DFS를 구현하는 문제네요. stack을 이용하면 재귀 없이 반복문만으로도 구현할 수 있습니다. 아래는 제가 간단히 풀어본 코드입니다.int ABC12::getMaxPoints(vector> &maze) { vector path(maze.size()); // stack으로 사용할 vector 배열. int max = -1; while(true) { int sum = 0; for (int i = 0; i < maze.size(); ++i) { sum += maze[i][path[i]]; } if (max < sum) { max = sum; } // backtracking int top; do { // 이전 단계와의 차이가 0일 때까지 path를 뒤에서 뺌 top = path.back(); path.pop_back(); } while(path.size() != 0 && top == path.back() + 1); if (path.size() == 0) { // 더 이상 둘러볼 다음 경우가 없는 경우 루프 탈출 break; } // 남은 분기가 있는 경우 다음 단계 경로 기록 int next = path.back()+1; while(path.size() != maze.size()) { path.push_back(next); } } return max; }(적고나니 단순히 푸는데만 집중해서 여러모로 코드가 더럽고, 일반적이지 못하며, 풀이 해설도 복잡해졌는데 양해 바랍니다. 헷갈리는 부분이 있다면 적어주세요.)풀이를 해설하면 일단 DFS에서 가장 중요한 backtracking을 구현하기 위해 현 반복 시점에서 어떠한 경로로 접근했는지를 저장하는 stack path를 정의하였습니다. (stack이 아니라 vector인 이유는 합산 계산할 때 임의접근할 필요가 있기 때문입니다.합산계산 코드나 최대값만 고르는 코드는 설명이 필요치 않을테니 넘어가고, backtracking을 위한 코드를 보면 일단 스택에서 최상위 값 하나를 추출합니다. 만약 추출한 값과 그 이전값이 동일하다면 추출한 값 대신 1 증가된 값을 넣어주고 다음 반복 주기를 돌리죠. 헌데 동일하지 않다면(즉 이미 한 번 1 증가해서 차이가 1이 나온 경우) 그 이전값도 추출해버립니다. 그 이전값을 1만큼 증가시키지 않으면 다음으로 갈 수 없으니까요. 같은 방식으로 동일한 값이 나올 때까지 쭉 추출하다가 동일한 값이 나오거나 아예 모든 값이 추출되면 반복문을 탈출합니다. 모든 값이 추출된 경우에는 모든 순회가 끝났다는 뜻이기도 하니 while(true)도 탈출해서 값을 반환하죠.아직 남은 값이 있는 경우(즉 남은 순회케이스가 있는 경우) 남아있는 값의 최후위 값 + 1만큼을 maze의 크기만큼 다시 채워준 뒤 다음 순회를 돌립니다.

C++ 핀볼 과제풀이 도움요청합니다..ㅜㅜ

1개의 답변

기타 목록