백준 16562 - 친구비(C++)

문제 링크입니다. https://www.acmicpc.net/problem/16562

16562번: 친구비

Union-Find로 풀 수 있는 문제입니다.

BFS를 사용해서 풀 수 있는 문제이기도 합니다. 저는 BFS를 이용해 푸는 방법을 설명해드리겠습니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <algorithm>

using namespace std;

int N, M, K;
int cost[10001];
vector<int> connect[10001];
int check[10001];
vector<int> Friend[10001];

bool cmp(int x, int y) {
    if (cost[x] < cost[y]) return true;
    else return false;
}

void bfs(int start, int line) {
    queue<int> q;
    q.push(start);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < connect[x].size(); i++) {
            int xx = connect[x][i];
            if (check[xx] == 0) {
                check[xx] = 1;
                Friend[line].push_back(xx);
                q.push(xx);
            }
        }
    }
}

void solve() {
    int line = 0;
    int require_cost = 0;
    for (int i = 1; i <= N; i++) {
        if (check[i] == 0) {
            check[i] = 1;
            Friend[line].push_back(i);
            bfs(i, line);
            line++;
        }
    }
    for (int i = 0; i < line; i++) {
        sort(Friend[i].begin(), Friend[i].end(), cmp);
        require_cost += cost[Friend[i][0]];
    }
    if (K >= require_cost) cout << require_cost;
    else cout << "Oh no";
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++) cin >> cost[i];
    for (int i = 1; i <= M; i++) {
        int x, y;
        cin >> x >> y;
        connect[x].push_back(y);
        connect[y].push_back(x);
    }
    solve();
    return 0;

}

 

 

질문 및 조언 댓글 남겨주세요