무인도 여행(23분)

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

구현 아이디어 3분 구현 20분
DFS나 BFS 둘 다 블러드 필이 가능할 듯한데 문제를 풀 때는 BFS가 먼저 떠올라서 BFS로 풀었다.

풀이(BFS)

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

using namespace std;

int check[101][101];

vector<int> solution(vector<string> maps) {
    vector<int> answer;
    
    int N = maps.size();
    int M = maps[0].size();
    
    for(int i = 0; i < N; ++i)
        for(int  j = 0; j < M; ++j)
        {
            if(maps[i][j] != 'X') check[i][j] = 1;
        }
    
    queue<pair<int, int>> Q;
    
    int di[4] = {-1, 0, 1, 0};
    int dj[4] = {0, 1, 0, -1};
    
    for(int i = 0; i < N; ++i)
        for(int  j = 0; j < M; ++j)
        {
            if(check[i][j] == 0) continue;
            Q.push(make_pair(i, j));
            
            check[i][j] = 0;
            int sum = maps[i][j] - '0';
            
            while(!Q.empty())
            {
                int cur_i = Q.front().first;
                int cur_j = Q.front().second;
                
                Q.pop();
                
                for(int k = 0; k < 4; ++k)
                {
                    int next_i = cur_i + di[k];
                    int next_j = cur_j + dj[k];
                    
                    if(next_i < 0 || next_j < 0 || next_i >= N || next_j >= M || check[next_i][next_j] == 0)
                        continue;
                    
                    Q.push(make_pair(next_i, next_j));
                    sum += (maps[next_i][next_j] - '0');
                    check[next_i][next_j] = 0;
                }
            }
            
            answer.push_back(sum);
        }
    
    if(answer.size() <= 0) answer.push_back(-1);
    else
        sort(answer.begin(), answer.end());
    
    return answer;
}

---

풀이(DFS)

재귀를 통한 DFS로 풀어봤다. 좀 더 깔끔한 풀이를 위해서 check 배열을 쓰지 않고 maps를 활용했다.

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

using namespace std;

int N, M;
int di[4] = {-1, 0, 1, 0};
int dj[4] = {0, 1, 0, -1};
vector<int> answer;
    
void DFS(int i, int j, int& sum, vector<string>& maps)
{
    sum += (maps[i][j] - '0');
    maps[i][j] = 'X';
    
    for(int k = 0; k < 4; ++k)
    {
        int next_i = i + di[k];
        int next_j = j + dj[k];
        
        if(next_i < 0 || next_j < 0 || next_i >= N || next_j >= M || maps[next_i][next_j] == 'X')
            continue;
        
        DFS(next_i, next_j, sum, maps);
    }
}

vector<int> solution(vector<string> maps) {
    N = maps.size();
    M = maps[0].size();
    
    // DFS로 풀어보자.
    for(int i = 0; i < N; ++i)
        for(int  j = 0; j < M; ++j)
            if(maps[i][j] != 'X') 
            {
                int sum = 0;
                DFS(i, j, sum, maps);
                answer.push_back(sum);
            }

    if(answer.size() <= 0) answer.push_back(-1);
    else
        sort(answer.begin(), answer.end());
    
    return answer;
}