종만북 외발 뛰기 (JumpGame) C++ 풀이 (코드제공)

1. 문제 설정 확인

종만북 드디어 대망의 챕터 8(많은 분들이 좌절한다는..) 첫 번째 문제다.

이 문제는 사실 DFS나 BFS로 풀어도 아무 문제가 없고, 실제로 백준의 단계별로 풀어보기 DFS항목에는 이와 비슷한 문제가 아주 많다. 하지만 여기선 책에 나오는대로 DP로 풀어보았다. 물론 DFS에나 BFS에도 이 기법을 이용하여 (메모이제이션) DP를 적용해 효율적으로 만드는 것도 가능하다. 이에 대해선 추후에 포스팅해보겠다.

첫 번째로 해야할것은 완전탐색으로 문제를 풀어보는 것이다. 이 부분은 매우 간단하다.

int JumpValue = field[x][y];
result = function(x + JumpValue, y) || function(x, y+ JumpValue);

이런식으로 그냥 y축으로 한 번, x축으로 한 번 뛴 결과를 재귀호출하여, 한 놈이라도 1을 return하면 result 값이 끝에 도달했다는 뜻이 된다. 하지만 이러면 당연히 한 칸 뛸때마다 계속해서 기저조건까지의 재귀호출이 일어나게 되고, 이는 당연히 효율적이지 못하다. 따라서 끝에 도달한 경우가 있다면, 그 케이스의 cache값을 1로 만들어 주어, 다음에 이 케이스를 호출한 경우도 바로 1을 return받을 수 있게 만든다. 이렇게 하면 (끝에 도달한 경우) 더 빠르게 값을 리턴하여 제일 윗 단 호출까지 돌아올 수 있다.

코드를 살펴보자면, x나 y값이 필드를 벗어나는 경우는 0을 리턴한다. 끝에 도달했으면, 1를 리턴한다. 또한 앞으로 DP문제에선 int&ret 이라는 포인터가 많이 등장할텐데, 이는 현재 cache값을 받아오는 동시에 ret = --- 을 통해 필요한 경우 직접 cache에 값을 덮어써 DP배열을 효율적으로 최신화하기 위함이다.

3. 해답 코드

#include <vector>
#include <iostream>
#include <string.h>
using namespace std;


int cache[101][101];

int solution(vector<vector<int>>& field, int size, int x, int y){
    if(x >= size || y >= size)
        return 0;
    int& ret = cache[x][y];
    if(field[x][y] == 0)
        return ret = 1;
    //이게
    if(ret != -1)
        return ret;
    //메모이제이션 코드 (없어도 동작하지만 완전탐색이 되어버림)
    int jump = field[x][y];
    return ret = solution(field, size, x + jump, y) || solution(field, size, x, y + jump);
}

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        vector<vector<int>>field;
        int size;
        cin >> size;
        for(int j = 0; j < size; j++){
            memset(cache, -1, sizeof(cache));
            vector<int> temp;
            for(int k = 0; k < size; k++){
                int tmp;
                cin >> tmp;
                temp.push_back(tmp);
            }
            field.push_back(temp);
        }
        if(solution(field, size, 0, 0) == 1)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
}

P.S. 만약 이 문제에서 사용한 재귀호출이 잘 이해가지 않는다면, 재귀호출에 대해 조금 더 공부하고 이 문제를 푸시는게 정신건강에(…) 이롭습니다. 사실 저도 백준을 시작하기 전 알고리즘 처음 잡았을 때 이 책을 샀다가 바로 이 문제에서 하차하고 백준 골드찍고 다시 잡은 케이스랍니다 :)

Source

종만북, 2022.07.22
CLion