[Programmers] 무인도 여행(LV.2)

풀이 소요시간 : 15분

자존감을 올려주는 꿀같은 탐색문제다. 같은 레벨 2 문제인데, DP 나 Greedy 와는 체감 난이도가 비교가 안된다. 그냥 내가 탐색문제를 좋아해서 그런것도 있는거같다. 전형적인 영역 정보 구하기 문제다.

전체 코드

#include <string>
#include <algorithm>
#include <vector>
#include <cstring>
#define INF 987654321
using namespace std;

vector<int> Vector;

int N, M;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int Map[101][101];
int Visit[101][101];

int Land = 0;
int Day = 0;


void Clear() {
    Day = 0;
}


void Dfs(int x, int y) {
    
    for(int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(nx < 1 || ny < 1 || nx > N || ny > M) continue;
        if(Visit[nx][ny] == 1) continue;
        if(Map[nx][ny] == INF) continue;
        
        Visit[nx][ny] = 1;
        Day += Map[nx][ny];
        Dfs(nx, ny);
        
    }
    
}


vector<int> solution(vector<string> maps) {
    
    N = maps.size(); // 세로
    M = maps[0].length(); // 가로
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(maps[i][j] == 'X') {
                Map[i+1][j+1] = INF;
            }
            else {
                Map[i+1][j+1] = maps[i][j] - '0';
            }
        }
    }
    //Map 초기화
    
    
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++) {
            if(Visit[i][j] == 1) continue;
            if(Map[i][j] == INF) continue;
            
            Visit[i][j] = 1;
            Land++; // 땅의 수
            Day += Map[i][j];
            Dfs(i, j);
            
            Vector.push_back(Day);
            Clear();
        }
    }
    //탐색
    
    
    
    if(Land == 0) {
        Vector.push_back(-1);
        return Vector;
    }
    else {
        sort(Vector.begin(), Vector.end());
        return Vector;
    }

}