프로그래머스 2023.09.05 (2Lv 무인도 여행)

프로그래머스

문제

---

문제 설명
메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.

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

제한사항
  ◈ 3 ≤ maps의 길이 ≤ 100
        ◈ 3 ≤ maps[i]의 길이 ≤ 100
        ◈ maps[i]는 'X' 또는 1 과 9 사이의 자연수로 이루어진 문자열입니다.
        ◈ 지도는 직사각형 형태입니다.

입출력 예

maps	result
["X591X","X1X5X","X231X", "1XXX1"]	[1, 1, 27]
["XXX","XXX","XXX"]	[-1]

예제 설명은 프로그래머스에 있는 해당 문제를 통해서 확인해주세요.

코딩

---

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

using namespace std;

int bfs(vector<string>& _vecMaps, vector<vector<bool>>& _vecVisit, int _iCol, int _iRow)
{
    // 반환할 식량
    int iFood = 0;
    // 해당 칸에서 접근가능한 4방향
    const int arrX[4] = { 1, 0, -1, 0 };
    const int arrY[4] = { 0, 1, 0, -1 };

    // bfs를 처리하기 위한 큐 선언
    queue<pair<int, int>> queue;
    queue.push(make_pair(_iCol, _iRow));
    _vecVisit[_iCol][_iRow] = true;

    while (!queue.empty())
    {
        int iCol = queue.front().first;
        int iRow = queue.front().second;
        queue.pop();
        
        iFood += (int)_vecMaps[iCol][iRow] - (int)'0';

        
        for (int i = 0; i < 4; ++i)
        {
            int iNewCol = iCol + arrX[i];
            int iNewRow = iRow + arrY[i];

            // 다음 등록될 인덱스의 범위가 주어진 map을 벗어나지 않는지 확인하고, 방문한 적이 없다면 등록한다.
            if ((iNewCol >= 0 && iNewCol < _vecMaps.size())
                && (iNewRow >= 0 && iNewRow < _vecMaps[0].length())
                && !_vecVisit[iNewCol][iNewRow]
                && _vecMaps[iNewCol][iNewRow] != 'X')
            {
                queue.push(make_pair(iNewCol, iNewRow));
                _vecVisit[iNewCol][iNewRow] = true;
            }
        }
    }

    return iFood;
}

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

    // 각 칸 마다 방문 처리를 해줄 vector
    vector<vector<bool>> vecVisit(maps.size());
    for (size_t vis = 0; vis < maps.size(); ++vis)
    {
        vecVisit[vis].resize(maps[vis].length(), false);
    }

    // 섬이 있는지 확인하기 위한 bool 변수
    bool bIsland = false;

    // 섬을 찾아가면서 bfs를 수행해 섬에 존재하는 모든 식량을 조사한다.
    for (size_t Col = 0; Col < maps.size(); ++Col)
    {
        for (size_t Row = 0; Row < maps[Col].length(); ++Row)
        {
            // 칸을 방문하지 않고, 해당 칸이 X(바다)가 아니라면
            if ((maps[Col][Row] != 'X')
                && !vecVisit[Col][Row])
            {
                bIsland = true;
                // 해당 섬의 식량을 조사해 정답으로 반환해줄 vector에 저장한다.
                answer.push_back(bfs(maps, vecVisit, Col, Row));
            }
        }
    }

    if (bIsland)
    {
        // 섬마다 식량 조사를 한 vector를 오름차순으로 정렬한다.
        sort(answer.begin(), answer.end(), less<int>());
    }
    else
    {
        answer.push_back(-1);
    }

    return answer;
}

얼마 전에 풀었던 미로 탈출 와 마찬가지로 BFS(너비 우선 탐색)을 이용해 풀어주었다.

우선 바다('X')가 아닌 칸을 찾아서 그 칸을 시작으로 BFS를 진행하고, BFS에서는 바다가 아닌 인접한 모든 칸을 조사해 인자로 주어진 maps의 해당 인덱스에 들어있는 식량 수를 취합해 반환해 주도록 만들었다.

 

이 문제에서는 방문기록을 초기화하지 않아도 되기 때문에 방문 처리 vector를 초기화해 주는 함수는 따로 만들지 않았다.

 

이후 모든 섬들의 식량이 취합된 answer를 sort() 함수를 이용해서 오름차순으로 정렬한 뒤, solution을 반환해 주었다.

 

이때, 접근할 수 없는 섬이 없는 경우는 bool 변수를 하나 만들어 섬이 없을 경우 -1을 answer에 push_back()해서 반환해 주었다.

 

 

 

 

이전에 미로 탈출 문제를 풀 때도 2차원 행렬 초기화를 보다 간단하게 하는 방법이 없는지 찾아봤는데, 다음과 같이 초기화를 해줄 수 있다.

vector<vector<bool>> vecVisit(maps.size(), vector<bool>(maps[0].length(),false));

 

실행 결과

---