[ 프로그래머스 ] 무인도 여행

문제

---

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

풀이

---

X와 숫자로 이루어진 2차원 배열을 그리드 형태로 변환, 지도를 순회한다. 방문 여부를 체크하면서 숫자로 이루어진 연결 요소(Connected Component) 별 크기를 측정 return한다.

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

using namespace std;

int isVisited[101][101];

int sum;

void Dfs(vector<string>maps, int y, int x)
{

    if (isVisited[y][x] == false )
    {
        if (maps[y][x] != 'X')
        {
            sum += ((maps[y][x]) - '0');
        }

        isVisited[y][x] = true;
    }

    else
    {
        return;
    }

    if (y > 0)
    {
        if (isVisited[y - 1][x] == false && maps[y - 1][x] != 'X')
        {
            Dfs(maps, y - 1, x);
        }

    }

    if (y < maps.size() - 1)
    {
        if (isVisited[y + 1][x] == false && maps[y + 1][x] != 'X')
        {
            Dfs(maps, y + 1, x);
        }
    }

    if (x > 0)
    {
        if (isVisited[y][x - 1] == false && maps[y][x - 1] != 'X')
        {
            Dfs(maps, y, x - 1);
        }
    }

    if (x < maps[y].size() - 1)
    {
        if (isVisited[y][x + 1] == false && maps[y][x + 1] != 'X')
        {
            Dfs(maps, y, x + 1);
        }
    }

    return;
}

vector<int> solution(vector<string> maps) 
{
    vector<int> answer;
    vector<int> failAnswer = { -1 };

    for (int i = 0; i < maps.size(); i++)
    {
        for (int j = 0; j < maps[i].size(); j++)
        {
            sum = 0;

            if (isVisited[i][j] == false)
            {
                if (maps[i][j] == 'X')
                {
                    isVisited[i][j] = true;
                    continue;
                }

                Dfs(maps, i, j);

                if (sum != 0)
                {
                    answer.push_back(sum);
                }
            }


        }
    }

    if (answer.size() == 0)
    {
        return { -1 };
    }

    sort(answer.begin(), answer.end());

    return answer;
}