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

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
 
using namespace std;
 
vector<int> answer;
bool check[101][101];
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
 
void bfs(vector<string> maps, int k, int j) {
    queue<pair<int,int>> q;
    q.push({k,j});
    check[k][j] = true;
    
    int result = 0;
    
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        result += (maps[x][y] - '0');
        q.pop();
        
        for(int i=0; i<4; i++) {
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            if(nx < 0 || ny < 0 || nx >= maps.size() || ny >= maps[k].size() || check[nx][ny]) {continue;}            
            if(maps[nx][ny] != 'X') {
                check[nx][ny] = true;
                q.push({nx,ny});    
            }
            
        }
    }
    
    answer.push_back(result);   
}
 
vector<int> solution(vector<string> maps) {
    for(int i=0; i<maps.size(); i++) {
        for(int j=0; j<maps[i].size(); j++) {
            if(maps[i][j] != 'X' && !check[i][j]) {
                bfs(maps,i,j);
            }
        }
    }
    
    sort(answer.begin(),answer.end());
    
    if(answer.size() == 0) { answer.push_back(-1); }
    return answer;
}

 

 

 

1. (0,0) 부터 시작하여 (0,1) (0,2) (0,3) ..... (1,0) (1,1) 과 같이 문자열 배열을 순회하며 'X' 가 아닐경우 bfs 탐색을 시작한다.

 

2. 탐색했던 섬을 다시 탐색하지 않기 위해서 bfs 탐색을 할때 bool check[101][101]  배열의 인덱스를 탐색시 true 로 바꿔준다. 

 

3. 탐색이 끝나면 결과값을 answer 벡터에 저장

 

4. answer를 오름차순 정렬