[Lv. 2] 무인도 여행

https://school.programmers.co.kr/learn/courses/30/lessons/154540

프로그래머스

이 문제는 DFS를 사용해서 해결할 수 있다.

문제에서 주어진 배열은 문자열 배열이므로 배열 순회 후 문자열을 순회하여도 해결할 수 있지만

DFS 과정 속에서 편리하게 해결하기 위해 문자열 배열의 요소를 2차원 배열로 변환하였다.

 

변환 과정은 다음과 같다.

1. X인 경우 0으로 변환한다.

2. 숫자인 경우 문자를 숫자로 변환한다.

 

DFS는 dx와 dy를 통해 상, 하, 좌, 우로 연결되는 칸은 탐색하였다.

remain 변수에 탐색 결과 연결된 칸에 저장된 값을 합하여 저장하였다.

answer 배열에 remain 변수에 저장된 값을 삽입하였다.

 

마지막으로 anawer 배열이 비어 있다면 -1을 삽입한다.

출력 시 오름차순으로 출력해야하므로 sort를 통해 오름차순으로 정렬하였다.

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int arr[101][101] = {0, };
bool visited[101][101] = {0, };
int dy[] = {-1, 1, 0, 0};
int dx[] = {0, 0, -1, 1};
int maxY, maxX;

void dfs(int y, int x, int& result){
    visited[y][x] = 1;
    result += arr[y][x];
    
    for(int i = 0;i<4;i++){
        int uy = y + dy[i];
        int ux = x + dx[i];
        if(uy<0||uy>=maxY||ux<0||ux>=maxX) continue;
        if(arr[uy][ux]){
            if(!visited[uy][ux])
                dfs(uy,ux,result);
        }
    }
}

vector<int> solution(vector<string> maps) {
    vector<int> answer;
    
    for(int i = 0;i<maps.size(); i++){
        string target = maps[i];
        for(int j = 0;j<target.length();j++){
            if(target[j] == 'X')
                arr[i][j] = 0;
            else
                arr[i][j] = target[j] - '0';
        }
    }
    maxY = maps.size();
    maxX = maps[0].length();
    

    for(int i = 0; i<maxY;i++){
        for(int j = 0;j<maxX;j++){
            int remain = 0;
            if(arr[i][j] != 0){
                if(!visited[i][j]){
                    dfs(i,j, remain);
                    answer.push_back(remain);
                }
            }
        }
    }
    if(answer.empty()){
        answer.push_back(-1);
    }
    sort(answer.begin(), answer.end());
    return answer;
}