'문제 ID : JUMPGAME' 에 대한 질문입니다.

  • otterton
    otterton

    안녕하세요.

    알고리즘 문제 해결 전략 책으로 공부하고 있는 학생입니다.

    일단 질문을 읽어주셔서 정말 감사합니다.

    먼저 문제에 대한 링크입니다.
    JUMPGAME

    저는 이 문제를 동적 계획법으로 해결하기 위해 다음과 같이 함수를 설계하였습니다.

    • 제가 작성한 알고리즘

    현재 보드판의 (x,y)에 위치하고 있을 때
    1. 종료 조건: 만약 보드판의 값이 0이면 true를 반환
    2-1. 아래쪽으로 이동할 수 있으면,
    아래쪽에 대한 메모값이 있는지 확인해보고 있으면 반환
    없으면 아래쪽에 대한 재귀 함수 호출 후 메모

    2-2. 오른쪽으로 이동할 수 있으면,
    오른쪽에 대한 메모값이 있는지 확인해보고 있으면 반환
    없으면 오른쪽에 대한 재귀 함수 호출 후 메모

    3. 아래, 오른쪽 둘다 갈 수 없으면 false를 반환

    위의 알고리즘 대로 실행한 결과 계속 오답이 뜨네요.
    저는 위에서 제시한 방법이 책에 소개된 알고리즘과 어떤 차이가 있는 것인지 궁금합니다.

    • 책에서 제시된 알고리즘

    현재 보드판의 (x,y)에 위치하고 있을 때
    1. 종료 조건: 보드판의 마지막 칸에 위치하고 있으면 true
    보드판 범위를 벗어나 있으면 false
    2. (x,y)에 대한 메모가 있으면 반환
    3. 메모가 없으면, 아래쪽에 대한 재귀함수 호출 || 오른쪽에 대한 재귀함수 호출을 계산한 결과를 메모 후 반환.

    제가 생각한 알고리즘과 책에서 나온 알고리즘의 차이점 :
    제가 생각한 알고리즘은 현재 보고 있는 좌표의 오른쪽과 아래쪽에 대해 메모를 확인하고 기록하는 것이고, 책에서 제시된 알고리즘은 현재 보고 있는 좌표에 대해 메모를 확인하고 기록한다는 점입니다.

    제 알고리즘의 문제점을 파악하지 못하고 있습니다.
    도움을 정중히 부탁드립니다 ..

    감사합니다!!

    • 제 알고리즘에 대한 소스코드입니다.
        #include <iostream>
#include <vector>

using namespace std;
int find(vector<vector<int>>& board, vector<vector<int>>& memoBoard, int x, int y);


int main(){
    int nTestCase;
    cin >> nTestCase;


    for (int t = 0; t < nTestCase; t++){
        int n;
        cin >> n;

        vector<vector<int>> board;
        std::vector<std::vector<int> > memoBoard(n, std::vector<int>(n, -1));

        for (int i = 0; i < n; i++){
            vector<int> tempV;
            int temp;
            for (int j = 0; j < n; j++){
                cin >> temp;
                tempV.push_back(temp);
            }
            board.push_back(tempV);
        }

        int result = find(board, memoBoard, 0, 0);
        if (result == 1)
            cout << "YES" << endl;
        else if (result == 0)
            cout << "NO" << endl;

    }
}


int find(vector<vector<int>>& board, vector<vector<int>>& memoBoard, int x, int y){
    int n = board.size();
    if (board[x][y] == 0)//종료 조건 1
        return 1; // "YES"



    int result = 0;
    int content = board[x][y];
    if (x + content < n){
        if (memoBoard[x + content][y] != -1)
            return memoBoard[x + content][y];
        result = memoBoard[x+content][y] = find(board, memoBoard, x + content, y);
    }
    if (y + content < n){
        if (memoBoard[x][y + content] != -1)
            return memoBoard[x][y + content];
        memoBoard[x][y+content] = find(board, memoBoard, x, y + content);
        result = result | memoBoard[x][y + content];
    }

    return result;
}

    7년 전
2개의 댓글이 있습니다.
  • keith
    keith

    재귀함수의 함정은, 탐색 순서가 DFS(깊이 우선)이라는 점인거 같습니다.
    Dynamic Programming의 경우, 탐색 순서가 Linear해야 하는데, 거기서 생기는 문제가 아닐까 싶습니다.
    즉, n,m위치에서 해당 위치에서 true인지 false인지는 n,m이후의 가질수 있는 경로의 경우의 수가 모두 확인이 되는 점화식이 성립해야 하는데, DFS로 탐색하는 경우, 해당 위치가 true인지 false인지는 아직 불확실합니다.
    제가 글재주가 없어서 좀 어렵게 설명했는데 도움이 되었으면 합니다.


    7년 전 link
  • otterton
    otterton

    답변해주셔서 정말 감사합니다.
    아직 정확히 이해는 되지 않지만 더 고민해보도록 할게요.

    감사합니다 !!


    7년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.