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

무인도 여행

문제 링크

무인도 여행

분석

2차원 배열이 주어집니다.
세로는 벡터, 가로는 스트링입니다.

X는 바다 숫자는 해당 땅에서 얻을 수 있는 식량입니다.
숫자는 1 ~ 9로 자연수입니다.

각각 연결된 땅들의 총 식량을 구해 오름차순으로 정렬하여 반환해야하는 문제입니다.
만약 섬이 존재하지 않는다면 -1을 반환해야합니다.

이동은 상하좌우가 가능합니다.

DFS나 BFS로 풀어볼 수 있습니다.
2차원 배열을 순회하면서 방문하지 않은 땅을 발견한다면, DFS/BFS를 수행합니다.
한 섬에서 얻을 수 있는 총 식량을 구하고 반환 배열에 값을 추가합니다.
모든 값을 찾았다면 정렬합니다.

예외는 섬이 존재하지 않는 경우입니다.

풀이

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

using namespace std;

// 반환할 답을 저장할 변수
vector<int> answer;

// 이동할 방향
int dx[4]{-1, 1, 0, 0};
int dy[4]{0, 0, -1, 1};

// 현재 위치에서 연결된 모든 땅을 탐색
int dfs(const vector<string>& maps, vector<vector<bool>>& visited, int y, int x)
{
    // 방문된 위치 저장 및 처리
    visited[y][x] = true;
    int sumFood = static_cast<int>(maps[y][x]) - '0';
    
    for (int i = 0; i < 4; ++i)
    {
        // 이동할 방향을 구한다.
        // 왼쪽, 오른쪽, 위, 아래 순서가 된다.
        int ny = y + dy[i];
        int nx = x + dx[i];
        
        // 배열을 벗어나지 않고, 방문한 적 없으며, 자연수인 인덱스를 방문
        if (ny >= 0 && nx >= 0 &&
            ny < maps.size() && nx < maps[0].size() &&
            visited[ny][nx] == false && 
            maps[ny][nx] != 'X')
        {
            sumFood += dfs(maps, visited, ny, nx);
        }
    }
    
    return sumFood;
}

vector<int> solution(vector<string> maps) {
    // 방문한 위치 저장할 변수
    vector<vector<bool>> visited(maps.size(), vector<bool>(maps[0].size(), false));
    
    // 모든 위치를 순회하면서 방문하지 않은 땅을 찾음
    for (int i = 0; i < maps.size(); ++i)
    {
        for (int j = 0; j < maps[0].size(); ++j)
        {
            if (visited[i][j] == false && maps[i][j] != 'X')
            {
                int islandFood = dfs(maps, visited, i, j);
                answer.push_back(islandFood);
            }
        }
    }
    
    // 섬이 없는 경우
    if (answer.size() == 0)
    {
        return {-1};
    }
    
    // 오름차순 정렬
    sort(answer.begin(), answer.end());
    
    return answer;
}

성능 요약

시간 복잡도는 $O(nm \ log \ (nm))$입니다.

• 모든 위치를 순회하면서 방문하지 않은 땅을 찾는 중첩 반복문 $O(nm)$
• dfs 함수의 호출 횟수 $O(nm)$
• answer 정렬 $O(nm \ log \ (nm))$
• $O(nm + nm + nm \ log \ (nm))$

공간 복잡도는 $O(nm)$입니다.

• 방문 여부를 저장하는 visited 배열 $O(nm)$
• dfs 함수의 재귀 호출 스택 $O(nm)$
• 정답을 저장하는 벡터 answer $O(nm)$
• $O(nm + nm + nm)$

테스트 1 〉 통과 (0.01ms, 4.19MB)
테스트 2 〉 통과 (0.01ms, 4.2MB)
테스트 3 〉 통과 (0.01ms, 4.21MB)
테스트 4 〉 통과 (0.02ms, 4.16MB)
테스트 5 〉 통과 (0.05ms, 3.64MB)
테스트 6 〉 통과 (0.08ms, 4.23MB)
테스트 7 〉 통과 (0.05ms, 3.66MB)
테스트 8 〉 통과 (0.13ms, 4.2MB)
테스트 9 〉 통과 (0.18ms, 4.22MB)
테스트 10 〉 통과 (0.18ms, 4.16MB)
테스트 11 〉 통과 (0.16ms, 4.21MB)
테스트 12 〉 통과 (0.25ms, 4.22MB)
테스트 13 〉 통과 (0.24ms, 4.18MB)
테스트 14 〉 통과 (0.37ms, 3.84MB)
테스트 15 〉 통과 (0.49ms, 4.14MB)
테스트 16 〉 통과 (0.45ms, 4.21MB)
테스트 17 〉 통과 (0.04ms, 4.14MB)
테스트 18 〉 통과 (0.44ms, 3.81MB)
테스트 19 〉 통과 (0.42ms, 4.19MB)
테스트 20 〉 통과 (0.08ms, 3.66MB)
테스트 21 〉 통과 (0.09ms, 3.62MB)
테스트 22 〉 통과 (0.01ms, 4.02MB)
테스트 23 〉 통과 (1.27ms, 4.25MB)
테스트 24 〉 통과 (0.35ms, 4.16MB)
테스트 25 〉 통과 (0.02ms, 3.63MB)