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

https://school.programmers.co.kr/learn/courses/30/lessons/154540

프로그래머스

오랜만에 보는 floodfill알고리즘이다. 42 so long 과제가 마지막... 이 문제의 경우 무인도 하나를 다 세고 다음 무인도를 찾아야 하므로 최대한 먼저 깊게 탐색하는 dfs가 알맞다. 먼저 무인도 cnt 세 주고 바다로 덮어버리기를 반복해 줬다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
vector<int> res;
int cnt = 0;
vector<string> map;
int xLen, yLen;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void    dfs(int x, int y) {
    cnt += map[x][y] - '0';
    map[x][y] = 'X';
    for (int i = 0; i < 4; i++) {
        if (x + dx[i] >= 0 && x + dx[i] < xLen 
            && y + dy[i] >= 0 && y + dy[i] < yLen 
            && map[x + dx[i]][y + dy[i]] != 'X') {
                dfs(x + dx[i], y + dy[i]);
        }
    }
}

vector<int> solution(vector<string> maps) {
    map = maps;
    vector<int> answer;
    xLen = map.size();
    yLen = map[0].size();
    for (int i = 0; i < xLen; i++) {
        for (int j = 0; j < yLen; j++) {
            if (map[i][j] != 'X') {
                dfs(i, j);
                answer.push_back(cnt);
                cnt = 0;
            }
        }
    }
    sort(answer.begin(), answer.end());
    if (answer.size() == 0)
        answer.push_back(-1);
    return answer;
}