[백준 BOJ] 16724번 - 피리 부는 사나이 (C++)

https://www.acmicpc.net/problem/16724

16724번: 피리 부는 사나이

dfs로 더이상 갈 곳이 없을 때까지 가는 방식으로 구현했다. 최적화를 안 시켜서 코드가 좀 더럽다. 탐색하다가 처음 가는 곳인데 다음에 갈 곳이 이미 한 번 갔던 곳이면 정답 개수를 하나 늘리면 된다.

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <memory.h>
#include <vector>

#define endl '\n'
#define ll long long
#define pii pair<int, int>
#define max 987654321

using namespace std;

int N, M;
char map[1000][1000];
vector<int> v[1000][1000];
bool ischeck[1000][1000];
int ans;

void dfs(int n, int m)
{
    if (ischeck[n][m])
    {
        return;
    }
    ischeck[n][m] = true;
    if (map[n][m] == 'D')
    {
        dfs(n + 1, m);
        if (v[n + 1][m].empty())
        {
            v[n][m].push_back(n);
            v[n][m].push_back(m);
            ans++;
        }
        else
        {
            v[n][m] = v[n + 1][m];
        }
        return;
    }
    else if (map[n][m] == 'U')
    {
        dfs(n - 1, m);
        if (v[n - 1][m].empty())
        {
            v[n][m].push_back(n);
            v[n][m].push_back(m);
            ans++;
        }
        else
        {
            v[n][m] = v[n - 1][m];
        }
        return;
    }
    else if (map[n][m] == 'R')
    {
        dfs(n, m + 1);
        if (v[n][m + 1].empty())
        {
            v[n][m].push_back(n);
            v[n][m].push_back(m);
            ans++;
        }
        else
        {
            v[n][m] = v[n][m + 1];
        }
        return;
    }
    else
    {
        dfs(n, m - 1);
        if (v[n][m - 1].empty())
        {
            v[n][m].push_back(n);
            v[n][m].push_back(m);
            ans++;
        }
        else
        {
            v[n][m] = v[n][m - 1];
        }
        return;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> M;
    string tmp;
    for (int n = 0; n < N; n++)
    {
        cin >> tmp;
        for (int m = 0; m < M; m++)
        {
            map[n][m]=tmp[m];
        }
    }
    for (int n = 0; n < N; n++)
    {
        for (int m = 0; m < M; m++)
        {
            dfs(n, m);
        }
    }
    cout<<ans<<endl;
    return 0;
}