[백준] 15559 - 내 선물을 받아줘

기존 값을 저장하고, 그걸 불러와야 답을 구할 수 있다... 그래서 메모이제이션이 중요하기 때문에 DP라고 생각함

1. 순차적으로 map을 검사하면서 방문하지 않은 지점이라면 DFS로 탐색

2. 방문한 지점이라면 그 방문한 지점의 값을 반환

3. 이렇게 끝까지 같다가 돌아오면 리턴된 값과 답을 비교하여 답을 찾아준다.

#include <iostream>
#define MAXSIZE 1002
using namespace std;
 
char map[MAXSIZE][MAXSIZE];
int visit[MAXSIZE][MAXSIZE];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
int N, M;
 
int dir(const char buff) {
    switch (buff) {
    case'N': return 0;
    case'S': return 1;
    case'W': return 2;
    case'E': return 3;
    default: return -1;
    }
}
 
int dfs(int x, int y, int cnt) {
    if (visit[y][x]) return visit[y][x];
    visit[y][x] = cnt;
    int d = dir(map[y][x]);
    int nx = x + dx[d], ny = y + dy[d];
    visit[y][x] = dfs(nx, ny, cnt);
    return visit[y][x];
}
 
int calc() {
    int ret = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            if (!visit[i][j]) {
                visit[i][j] = dfs(j, i, ret + 1);
                ret = ret > visit[i][j] ? ret : visit[i][j];
            }
    return ret;
}
 
int main(void) {
    cin >> N >> M;
    for (int i = 0; i < N; i++) cin >> map[i];
    cout << calc() << '\n';
    return 0;
}