외발 뛰기(JUMPGAME)

https://algospot.com/judge/problem/read/JUMPGAME

2가지 방법의 코드가 있다.

첫 번째는 내가 푼 BFS 방식이고,

두 번째는 책에 나와있는 재귀 호출(동적 계획법, 메모이제이션)로 푼 방식이다.

참고로, 첫 번째 코드(BFS)의 18 ~ 19번 째 줄 dy, dx 배열은 지워도 된다. 안 쓰였음. (왜 안 지웠지?)

BFS

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int Map[102][102] = { 0, };
 
int N = 0;
 
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
 
bool BFS()
{
    queue<pair<int, int> > q;
 
    bool visit[102][102] = { false, };
 
    q.push({ 0, 0 });
 
    visit[0][0] = true;
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int r = q.front().first;
            int c = q.front().second;
 
            q.pop();
 
            if (r == N - 1 && c == N - 1) return true;
 
            int ny = r + Map[r][c];
            int nx = c + Map[r][c];
            
            if (0 <= ny && ny < N && !visit[ny][c])
            {
                q.push({ ny, c });
                visit[ny][c] = true;
            }
 
            if (0 <= nx && nx < N && !visit[r][nx])
            {
                q.push({ r, nx });
                visit[r][nx] = true;
            }
        }
    }
 
    return false;
}
 
int main(void)
{
    int T = 0;
 
    scanf("%d", &T);
 
    while (T--)
    {
        memset(Map, 0, sizeof(Map));
 
        scanf("%d", &N);
 
        for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) scanf("%d", &Map[i][j]);
 
        if (BFS()) printf("YES\n");
        else printf("NO\n");
    }    
 
    return 0;
}

동적 계획법(메모이제이션)

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int Map[102][102] = { 0, };
int cache[102][102] = { 0, };
 
int N = 0;
 
int jump(int y, int x)
{
    if (y >= N || x >= N) return 0;
 
    if (y == N - 1 && x == N - 1) return 1;
 
    int & ret = cache[y][x];
 
    if (ret != -1) return ret;
 
    int jumpSize = Map[y][x];
 
    return ret = (jump(y, x + jumpSize) || jump(y + jumpSize, x));
}
 
int main(void)
{
    int T = 0;
 
    scanf("%d", &T);
 
    while (T--)
    {
        scanf("%d", &N);        
        
        memset(Map, 0, sizeof(Map));
 
        for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)    cache[i][j] = -1;
 
        for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)    scanf("%d", &Map[i][j]);
        
        if (jump(0, 0) == 1) printf("YES\n");
        else printf("NO\n");
    }    
 
    return 0;
}