[프로그래머스 2레벨] 무인도 여행 (C++)

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

using namespace std;

int dy[] = {0, 0, 1, -1};
int dx[] = {1, -1, 0, 0};
int visited[101][101];

vector<int> solution(vector<string> maps) {
    vector<int> answer;

    for(int i=0; i<maps.size(); i++)
    {
        for(int j=0; j<maps[i].size(); j++)
        {
            if(maps[i][j] == 'X' || visited[i][j]) continue;
            queue<pair<int ,int>>q;
            q.push({i, j});
            visited[i][j] = 1;
            int sum = maps[i][j]-'0'; //누적합용 변수, 시작 값 저장

            while(!q.empty())
            {
                auto [y, x] = q.front();
                q.pop();

                for(int k=0; k<4; k++)
                {
                    int ny = y + dy[k];
                    int nx = x + dx[k];

                    if(nx < 0 || nx >= maps[i].size() || ny < 0 || ny >= maps.size()) continue;
                    if(maps[ny][nx] == 'X' || visited[ny][nx]) continue;

                    q.push({ny, nx});
                    visited[ny][nx] = 1;
                    sum += maps[ny][nx] - '0';
                }
            }
            answer. push_back(sum);
        }
    }
    sort(answer.begin(), answer.end());
    if(answer.size()==0) answer.push_back(-1);
    return answer;
}

 

기본적인 bfs 문제이다.

주어진 maps 값을 기준으로 숫자 일때 bfs 탐색을 돌려주면 된다.

탐색을 돌릴 때는 중복을 방지하기 위해 방문 배열을 통해 방문 여부를 체크해준다.

 

그리고 가능한 생존 일수를 체크하기 위해 bfs 탐색을 돌리며 누적합 또한 추가로 계산해주고,

bfs 탐색을 마치면 구했던 누적합을 answer에 넣어준다.

 

문제에 주어진 조건에 따라 가능한 경우가 없다면 -1을 넣어주고, 이미 값이 있다면 오름차순 정렬을 해주면 된다.