[Algorithm]Baekjoon 16562번 :: 친구비

https://www.acmicpc.net/problem/16562

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
 
struct Node
{
    int num;
    int cost;
};
 
bool cmp(const Node& a, const Node& b)
{
    return a.cost < b.cost;
}
 
int n, m, k, v, w, cost;
bool visited[10001] = { false };
vector<vector<int>> graph;
vector<Node> nodes;
 
void DFS(int index)
{
    for (int i = 0; i < graph[index].size(); ++i)
    {
        int childNode = graph[index][i];
 
        if (visited[childNode]) continue;
        
        visited[childNode] = true;
        DFS(childNode);
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m >> k;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> cost;
        nodes.push_back({ i, cost });
    }
 
    sort(nodes.begin(), nodes.end(), cmp);
 
    graph.resize(n + 1);
 
    for (int i = 0; i < m; ++i)
    {
        cin >> v >> w;
 
        graph[v].push_back(w);
        graph[w].push_back(v);
    }
 
    int answer = k;
 
    for (int i = 0; i < nodes.size(); ++i)
    {
        int index = nodes[i].num;
 
        if (visited[index]) continue;
 
        if (nodes[i].cost > k)
        {
            cout << "Oh no";
            return 0;
        }
 
        k -= nodes[i].cost;
 
        visited[index] = true;
        DFS(index);
    }
 
    cout << answer - k;
}
 
 

 

친구의 친구는 친구다... 라는 말은 뎁스2까지만 친구라는게 아니라, 그냥 연결된 모든것들은 다 친구라는 것이다.

 

즉, 주어지는 입력값들을 토대로 그래프를 만들면 결국 독립된 양방향 그래프가 최대 n개가 나온다.

1 1 이렇게 자기자신이 주어지는 경우도 있다고 하니 최대 n개가 나오는 게 맞다.

 

이 독립된 양방향그래프는 어디서 시작하든 이어진것들은 전부 다 탐색된다. 

그런데 이 때, 최소값으로 구해야하니 반드시 제일 cost가 작은걸 선택해야 한다.

이렇게 각 그래프당 제일 값이 작은 노드 한개씩 구해서 전부 더했을 때, k값보다 작으면 정답이 된다.

 

그래서 애초에 처음부터 값을 기준으로 오름차순 정렬시키고 모든 노드가 탐색됐을 때의 값이 정답이 된다.