C++:: 프로그래머스 <무인도 여행>

bfs에 친숙하다면 쉽게 풀 수 있는 문제이다. 다른 방식으로도 구현 가능하지만(dfs와 같은 다른 flood fill 방식) bfs가 편할거같아서 다음과 같이 구현했다.

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
bool vis[100][100];

vector<int> solution(vector<string> maps)
{
    vector<int> answer;
    int n = maps.size(), m = maps[0].size();
    queue<pair<int,int>> q;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if (!isdigit(maps[i][j]) || vis[i][j]) continue;// 방문했거나 섬이 아니면 
            int day = maps[i][j] - '0';// 섬에 있을 수 있는 날짜 초기화
            q.push({i,j});
            vis[i][j] = true;//방문 체크
            while(!q.empty())
            {
                pair<int,int> cur = q.front();
                q.pop();
                for(int dir=0;dir<4;dir++)
                {
                    int nx = cur.first + dx[dir];
                    int ny = cur.second + dy[dir];
                    if(nx<0 || ny<0 || nx>=n || ny>=m) continue;//범위 넘어가면
                    if(vis[nx][ny] || !isdigit(maps[nx][ny])) continue;// 방문했거나 섬이아니면
                    vis[nx][ny] = true;// 방문 체크
                    q.push({nx,ny});//큐에 넣어주기
                    day += maps[nx][ny] - '0';//섬에 있을수 있는 날짜 추가
                }
            }
            answer.push_back(day);
        }
    }
    if(answer.empty()) answer.push_back(-1);//비어있으면 섬이 없으니 -1 추가
    else sort(answer.begin(), answer.end());// 오름차순 정렬
    return answer;
}