[코딩테스트] 23/12/12 - 무인도 여행 (Level2)

🌜 프로그래머스 링크

문제 설명

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

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

제한사항

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

Github 링크

문제풀이

• BFS를 사용하여 문제 풀이하였습니다.
  • visited 배열로 방문여부를 판단합니다.

참고할 문서

BFS-DFS

코드 (C++)

int BFS(vector<string> maps, vector<vector<bool>>& visited, int y, int x)
{
    int dr[] = {1, -1, 0, 0};
    int dc[] = {0, 0, 1, -1};
    queue<pair<int, int>> q;
    q.emplace(x, y);
    visited[x][y] = true;
    int countDay = 0;
    while (!q.empty())
    {
        pair<int, int> temp = q.front();
        q.pop();
        countDay += maps[temp.second][temp.first] - '0';
        for (int index = 0; index < 4; ++index)
        {
            int nx = temp.first + dr[index];
            int ny = temp.second + dc[index];
            if (ny >= maps.size() || ny < 0 || nx >= maps[ny].size() || nx < 0) 
                continue;
            if (visited[nx][ny] || maps[ny][nx] == 'X')
                continue;
            
            visited[nx][ny] = true;
            q.emplace(nx, ny);
        }
    }
    return countDay;
}
vector<int> solution(vector<string> maps) {
    vector<int> answer;
    vector<vector<bool>> visited(maps[0].size(), vector<bool>( maps.size(), false));
    for (int y = 0; y < maps.size(); ++y)
    {
        for (int x = 0; x < maps[y].size(); ++x)
        {
           
            //바다임
            if (maps[y][x] == 'X' || visited[x][y])
                continue;
            
            answer.push_back(BFS(maps, visited, y, x));
        }
    }
    if (answer.empty())
        answer.push_back(-1);
    
    reverse(answer.begin(), answer.end());
    return answer;
}