이승민의 개발 블로그

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

int solution(int n, vector<vector<int>> costs) {
    vector<vector<pair<int, int>>> graph(n);
    
    for (auto& edge : costs)
    {
        int u = edge[0], v = edge[1], cost = edge[2];
        graph[u].push_back({cost, v});
        graph[v].push_back({cost, u});
    }
    
    int totalCost = 0;
    vector<bool> visited(n, false);
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    visited[0] = true;
    for (auto& edge : graph[0])
    {
        pq.push(edge);
    }
    
    while (!pq.empty())
    {
        auto [cost, next] = pq.top();
        pq.pop();
        
        if (visited[next] == true)
            continue;
        
        visited[next] = true;
        totalCost += cost;
        
        for (auto& edge : graph[next])
        {            
            if (visited[edge.second] == false)
                pq.push(edge);
        }
    }
    
    return totalCost;
}

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int visited[200];
int answer = 0;

void dfs(vector<vector<int>>& connects, int idx, int group)
{
    if (visited[idx] != 0)
    {
        return ;        
    }
    
    visited[idx] = group;
    for (auto& c : connects[idx])
    {
        if (visited[c] == 0)
            dfs(connects, c, group);
    }
}

int solution(int n, vector<vector<int>> computers) {
    
    vector<vector<int>> connects(n, vector<int>());
    
    for (int i = 0; i < n; i++)
    {
        // cout << i << " ";
        for (int j = 0; j < n; j++)
        {
            if (i == j)
                continue;
            if (computers[i][j] == 1)
            {
                connects[i].push_back(j);
                // cout << j << " ";
            }
        }
        // cout << endl;
    }
    
    for (int i = 0; i < n; i++)
    {
        visited[i] = 0;
    }
    
    for (int i = 0; i < n; i++)
    {
        if (visited[i] == 0)
        {
            answer++;
            dfs(connects, i, answer);
        }
    }
    
    return answer;
}

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

vector<int> solution(vector<int> prices) {
    int n = prices.size();
    vector<int> answer(n, 0);
    
    // index, price, second
    queue<pair<pair<int, int>, int>> q;
    
    q.push({{0, prices[0]}, 0});
    for (int i = 1; i < n; i++)
    {
        int q_size = q.size();
        while (q_size > 0)
        {
            auto [index_price, second] = q.front();
            q.pop();
            
            int index = index_price.first;
            int price = index_price.second;
            second++;
            if (price <= prices[i])
            {
                q.push({{index, price}, second});
            }
            else
            {
                answer[index] = second;
            }
            q_size--;
        }
        
        q.push({{i, prices[i]}, 0});
    }
    
    while (!q.empty())
    {
        auto [index_price, second] = q.front();
        q.pop();
        
        int index = index_price.first;
        answer[index] = second;
    }
    
    return answer;
}

#include <vector>
#include <queue>
#include <iostream>

using namespace std;

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

int visited[100][100];

int solution(vector<vector<int> > maps)
{
    int answer = 100 * 100 + 1;
    int n = maps.size(), m = maps[0].size();
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            visited[i][j] = 0;
    }
    
    // pos, depth
    queue<pair<pair<int, int>, int>> q;
    q.push({{n - 1, m - 1}, 1});
    
    while(!q.empty())
    {
        auto [pos, depth] = q.front();
        q.pop();
        
        int h = pos.first, w = pos.second;
        if (h == 0 && w == 0)
        {
            answer = min(answer, depth);
            continue;
        }
        
        if (depth >= answer)
            continue;
        
        if (visited[h][w] == 1)
            continue;
        visited[h][w] = 1;
        for (int i = 0; i < 4; i++)
        {
            int nextY = h + dy[i];
            int nextX = w + dx[i];
            
            if (nextY < 0 || nextY > n - 1 || nextX < 0 || nextX > m - 1 || maps[nextY][nextX] == 0 || visited[nextY][nextX] == 1)
                continue;
            
            q.push({{nextY, nextX}, depth + 1});
        }
    }
    
    return answer == 10001 ? -1 : answer;
}