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

< 해설 >

bfs로 해결한 문제이다. 이렇게 2X2 배열로 탐색해야 하는 문제는 BFS로 풀게되는것 같다. 

bool 로 2*2 배열을 두었다. 그리고 2중 for문을 돌면서 배열을 모두 탐색하되 처음으로 true를 만나면 BFS를 바로 돈다. 그렇게 BFS 를 돌고 나오면 근접 위치들은 전부다 false가 된 상태일 테니 말이다.

이렇게 2중 for문으로 배열을 한번 탐색하면 답이 나온다.

 

내가 풀은 답안에 대해 좀더 설명하자면 BFS 진입 시에 answer 벡터에 push_back 으로 시작지점의 값을 넣어준다. 그리고 파라미터로 인접 인덱스들의 값을 저장시킬 벡터의 index도 넘겼다. 이러면 BFS 내부에서는 벡터의 인덱스에 접근해서 값을 + 해주기만 하면 되니까 굉장히 편리하다.

 

< 문제 >

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

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

 

입출력 예 설명

입출력 예 #1

위 문자열은 다음과 같은 지도를 나타냅니다.

연결된 땅들의 값을 합치면 다음과 같으며

이를 오름차순으로 정렬하면 [1, 1, 27]이 됩니다.

 

 

< 풀이 >

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

using namespace std;

vector<int> answer = { -1 };
bool boolcheck[101][101];
queue<pair<int, int>> task; // x, y좌표

int defense[4][2] = { {1,0}, {0,1}, {-1,0}, {0, -1} };

void BFS(const vector<string>& maps, int answerIdx)
{
    while (!task.empty())
    {
        int curX = task.front().first;
        int curY = task.front().second;
        task.pop();

        for (int i = 0; i < 4; i++)
        {
            int nextX = curX + defense[i][0];
            int nextY = curY + defense[i][1];

            if (nextX < 0 || nextY < 0 || nextX >= maps.size() || nextY >= maps[0].size()
                || false == boolcheck[nextX][nextY])
                continue;

            task.push(make_pair(nextX, nextY));
            boolcheck[nextX][nextY] = false;

            char c_number = maps[nextX][nextY];
            int i_number = c_number - '0';
            answer[answerIdx] += i_number;
        }
    }
}

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

    for (int i = 0; i < maps.size(); i++)
        for (int m = 0; m < maps[i].size(); m++)
            if (maps[i][m] != 'X')
                boolcheck[i][m] = true;


    for (int i = 0; i < maps.size(); i++)
    {
        for (int m = 0; m < maps[i].size(); m++)
        {
            if (boolcheck[i][m])
            {
                boolcheck[i][m] = false;
                task.push(make_pair(i, m));

                char c_number = maps[i][m];
                int i_number = c_number - '0';
                answer.push_back(i_number);

                BFS(maps, answer.size() - 1);
            }
        }
    }

    if (answer.size() != 1)
    {
        vector<int> returnvec;
        returnvec.assign(answer.begin()+1, answer.end());
        copy(answer.begin()+1, answer.end(), returnvec.begin());
        sort(returnvec.begin(), returnvec.end());
        return returnvec;
    }

    return answer;
}