[C++][백준 16562] 친구비

문제

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

접근 방법

친구의 친구는 친구라는 규칙으로 인해 한 명의 친구를 사귀면 그 친구와 간접적으로 연결된 모든 친구는 친구가 됩니다.
하나의 그룹이 만들어졌다고 볼 수 있고 그룹에 속한 친구는 친구비를 낼 필요가 없다는 점에 주목하면 됩니다.

코드

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

int N, M, k, costSum;
int A[10001];
vector<int> graph[10001];
bool isVisited[10001];
queue<int> q;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> N >> M >> k;
    for (int i = 1; i <= N; ++i)
    {
        cin >> A[i];
    }

    while (M--)
    {
        int v, w;
        cin >> v >> w;
        graph[v].push_back(w);
        graph[w].push_back(v);
    }

    for (int i = 1; i <= N; ++i)
    {
        if (isVisited[i])
        {
            continue;
        }

        q.push(i);
        int cost = A[i];

        while (!q.empty())
        {
            int curFriend = q.front();
            q.pop();

            for (int nextFriend : graph[curFriend])
            {
                if (isVisited[nextFriend])
                {
                    continue;
                }

                isVisited[nextFriend] = true;
                q.push(nextFriend);

                cost = min(cost, A[nextFriend]);
            }
        }

        costSum += cost;
    }

    if (costSum <= k)
    {
        cout << costSum;
    }
    else
    {
        cout << "Oh no";
    }
    return 0;
}

풀이

아직 탐색되지 않은 친구는 그래프 탐색을 하여서 연결된 모든 친구를 탐색하고 최소 친구비를 찾아내어서 더해줍니다.
탐색된 친구는 무시하면 됩니다.