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

BFS 접근법:

방문하지 않은 섬이 있는 확인한다.
방문하지 않은 섬이 있다면 BFS를 통해 섬의 모든 지점을 방문해 식량을 계산한다.
계산한 식량을 모두 더해 결과를 리턴한다.
리턴된 결과를 Answer에 담는다.
Answer가 비었다면 -1 을 리턴한다.
정렬한뒤 리턴한다.

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

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

int bfs(int cx, int cy, int n, int m, vector<vector<bool>>& visited, const vector<string>& maps)
{
    int sum = maps[cx][cy] - '0';
    queue<pair<int, int>> q;
    q.push({cx, cy});
    visited[cx][cy] = true;
    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;

        q.pop();
        
        for(int i = 0; i < 4; ++i)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && nx < n && ny >= 0 && ny < m)
            {
                if(maps[nx][ny] != 'X' && !visited[nx][ny])
                {
                    q.push({nx, ny});
                    visited[nx][ny] = true;        
                    sum += maps[nx][ny] - '0';
                }
            }
        }    
    }
    return sum;
}

vector<int> solution(vector<string> maps) {
    vector<int> answer;
    int n = maps.size();
    int m = maps[0].size();
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < m; ++j)
        {
            if(maps[i][j] != 'X' && !visited[i][j])
            {
                answer.push_back(bfs(i, j, n, m, visited, maps));
            }
        }
    }
    if(answer.empty()) return { -1 };
    sort(answer.begin(), answer.end());
    return answer;
}

DFS 접근법:

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

using namespace std;

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

int dfs(int cx, int cy, int n, int m, vector<vector<bool>>& visited, const vector<string>& maps) {
    // 1. 현재 위치 방문 처리 및 식량 합산
    visited[cx][cy] = true;
    int sum = maps[cx][cy] - '0';

    // 2. 상하좌우 인접한 땅 탐색
    for(int i = 0; i < 4; ++i) {
        int nx = cx + dx[i];
        int ny = cy + dy[i];

        // 3. 맵 범위를 벗어나지 않고
        if(nx >= 0 && nx < n && ny >= 0 && ny < m) {
            // 4. 바다가 아니며('X'가 아님), 아직 방문하지 않은 땅이라면
            if(maps[nx][ny] != 'X' && !visited[nx][ny]) {
                // 재귀적으로 다음 땅을 탐색하고 식량을 누적
                sum += dfs(nx, ny, n, m, visited, maps);
            }
        }
    }
    
    return sum;
}

행렬 테두리 회전하기[프로그래머스]

괄호 변환[프로그래머스]