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

프로그래머스

지도를 나타낸는 문자열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 

result : [1, 1, 27]

 

 

풀이 방법

BFS나 DFS를 이용해서 연결되어 있는 섬을 찾은 후

연결된 섬들의 머물 수 있는 시간을 배열에 담아줍니다.

이후 정렬하여 반환하여 마무리합니다.

 

BFS 코드

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

int BFS(vector<string>& maps, vector<vector<bool>>& visited, int y, int x)
{
    int ret = 0;
    
    queue<pair<int, int>> q;
    visited[y][x] = true;
    q.push({y, x});
    
    while(!q.empty())
    {
        auto [cy, cx] = q.front(); q.pop();
        ret += maps[cy][cx] - '0';
        
        for (int i = 0; i < 4; i++)
        {
            auto [ny, nx] = make_pair(cy + dy[i], cx + dx[i]);
            
            // 배열 범위를 넘어갔거나, 이미 방문을 했거나, X라면 continue
            if (ny < 0 || ny >= visited.size() || nx < 0 || nx >= visited[ny].size() 
                || visited[ny][nx] || maps[ny][nx] == 'X')
                continue;
            
            visited[ny][nx] = true;
            q.push({ny, nx});
        }
        
    }
    return ret;
}

 

 

solution 코드

vector<int> solution(vector<string> maps) {
    vector<int> answer;
    vector<vector<bool>> visited(maps.size(), vector<bool>(maps[0].size()));
    
    // X가 아니면서 방문하지 않은 섬을 기준으로 체크
    for (int i = 0; i < maps.size(); i++)
    {
        for (int j = 0; j < maps[i].size(); j++)
        {
            if (visited[i][j] || maps[i][j] == 'X')
                continue;
            
            answer.push_back(BFS(maps, visited, i, j));
        }
    }
    
    // 연결된 섬에서 머물 수 있는 시간들을 정렬
    sort(answer.begin(), answer.end());
    
    // 머물 수 있는 섬이 없다면 -1을 추가
    if (answer.size() == 0)
        answer.push_back(-1);
    
    return answer;
}