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

프로그래머스

 

• 각 칸의 숫자는 해당 칸에서 최대 며칠 머물 수 있는지 나타냄
• 이어진 땅들은 하나의 무인도
• X는 갈 수 없음

> bfs를 이용한 풀이

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

using namespace std;

vector<int> answer;

char board[101][101] = {'0'};
bool check[101][101] = {false};

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

void bfs(int posX, int posY, int width, int height) {
    queue<pair<int, int>> q;
    q.push({posX, posY});
    check[posX][posY] = true;
    
    int sum = 0;
    
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;

        sum += board[x][y] - '0';
        
        q.pop();
        
        for(int i = 0; i < 4; i++) {
            int curX = x + dx[i];
            int curY = y + dy[i];
            
            if(curX < 0 || curX >= width || curY < 0 || curY >= height || check[curX][curY] || board[curX][curY] == 'X') continue;
            
            check[curX][curY] = true;
            q.push({curX,curY});
        }
    }
    
    answer.push_back(sum);
}

vector<int> solution(vector<string> maps) {
    int width = maps.size();
    int height = maps[0].size();
    
    for(int i = 0; i < width; i++)
        for(int j = 0; j < height; j++)
            board[i][j] = maps[i][j];
    
    for(int i = 0; i < width; i++) {
        for(int j = 0; j < height; j++) {
            if(!check[i][j] && maps[i][j] != 'X')
                bfs(i, j , width, height);
        }
    }
    
    sort(answer.begin(), answer.end());
    
    if(answer.empty()) {
        answer.push_back(-1);
        return answer;
    }
    else
        return answer;
}