프로그래머스 / 무인도 여행 / C++

그래프 탐색 문제에서 보통 BFS를 많이 사용했었기 때문에 DFS로 풀어봤습니다.

DFS에 지금까지의 날짜를 누적해가면서 넘기는 경우에는, 지도 형태에 따라 끊기는 경우가 있기 때문에, 이 부분은 조심해야 합니다.

#include <string>
#include <vector>
#include <climits>
#include <algorithm>
 
using namespace std;
 
//d를 가지고 다니면 끊겼을때 제대로 더해지지 않으니 조심!
 
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int N,M;
int visited[100][100];
int dist = 0;
 
void DFS(int x,int y,vector<string>& maps)
{
    visited[x][y] = 1;
    dist += maps[x][y]-'0';
    
    for (int i=0;i<4;i++)
    {
        int nX = x + dx[i];
        int nY = y + dy[i];        
        
        if (nX < 0 || nX >= N || nY < 0 || nY >= M || maps[nX][nY] == 'X')
            continue;
        if (visited[nX][nY] == 1)
            continue;       
        
        DFS(nX,nY,maps);
    }
}
 
vector<int> solution(vector<string> maps) {
    vector<int> answer;
    N = maps.size();
    M = maps[0].length();
    
    for (int i=0;i<N;i++)
    {
        for (int j=0;j<M;j++)
        {
            if (maps[i][j] != 'X' && visited[i][j] == 0)
            {
                DFS(i,j,maps);
                answer.push_back(dist);
                dist = 0;
            }   
        }
    }
    
    sort(answer.begin(),answer.end());
    
    if (answer.empty())
    {
        answer.push_back(-1);
    }
        
    return answer;
}