[백준] 1103 게임

#pragma warning(disable:4996)
#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
#include <random>
#include<time.h>
#include<string>
#include<queue>
#include <set>
#include <map>
#include <list>
#include<stack>
#include<deque>
#include<cstring>
#define SIZE 52
#define MAX(X, Y) (X) > (Y) ? (X) : (Y)
using namespace std;

int mapp[SIZE][SIZE], dp[SIZE][SIZE], visited[SIZE][SIZE];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
int N, M;

int dfs(int y, int x) {
    if (y < 0 || x < 0 || y >= N || x >= M || !mapp[y][x])
        return 0;
    if (visited[y][x]) { cout << -1 << endl; exit(0); }
    if (dp[y][x])return dp[y][x];

    visited[y][x] = 1;
    for (int dir = 0; dir < 4; dir++) {
        dp[y][x] = MAX(dp[y][x], dfs(y + dy[dir] * mapp[y][x], x + dx[dir] * mapp[y][x]) + 1);
    }
    visited[y][x] = 0;
    return dp[y][x];


}

int main(void) {
    cin >> N >> M;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) {
            char c;
            cin >> c;
            if (c <= '9') mapp[i][j] = c - '0';
        }

    cout << dfs(0, 0) << endl;

    return 0;
}

- DFS의 경우, 기본적으로 파고 들어가는 것이기 때문에, 전후 처리가 필요한 경우가 있다. 그 역할을 하는 것이 여기서는 visited.

- 또한 dp 값이 있는 점의 경우, visited가 있거나 없거나 가능성이 있지만, visited가 있는 점의 경우 무조건 dp 값은 존재하기 때문에, 무한 loop를 방지하기 위해서는 visited를 체크하고 dp를 체크하여 메모리의 낭비가 없도록 합니다.

 

lcs11244.tistory.com/63 참조 많이 함.