[백준] 친구비 16562번 (c++) bfs

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

 

풀이 방법

간단한 bfs문제이다.
친구의 친구도 친구, 친구의 친구의 친구도 친구 이므로 bfs를 통해 친구 그룹을 만든 후 그 친구들 중 친구비가 가장 작은 값을 구해서 더해주면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
#include <queue>

using namespace std;

int N, M, K;
vector<int> money;
vector<vector<int> > f;
int visited[10001];

int bfs(int idx) {
    int min_money = money[idx]; // 현재 친구 그룹에서 가장 작은 값

    queue<int> q;
    q.push(idx);
    visited[idx] = 1;

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

        for (int i = 0;i < f[now].size();i++) {
            int next = f[now][i];
            if (visited[next] == 0) {
                q.push(next);
                visited[next] = 1;
                min_money = min(min_money, money[next]);
            }
        }

    }
    return min_money;
}

int main() {
    cin >> N >> M >> K;
    memset(visited, 0, sizeof(visited));
    money.push_back(0); // 인덱스를 위한 가비지 값 채워 넣기
    f.resize(N+1);
    for (int i = 0;i < N;i++) { //친구 비 입력 인덱스는 1부터 시작한다.
        int a;
        cin >> a;
        money.push_back(a);
    }
    
    for (int i = 0;i < M;i++) { //친구 관계 입력 받기
        int a, b;
        cin >> a >> b;
        f[a].push_back(b);
        f[b].push_back(a);
    }

    // bfs를 돌며 그룹 묶기 그 중 친구비가 가장 싼 친구랑 친구하기
    int ans = 0;
    for (int i = 1;i < N+1;i++) {
        if(visited[i] == 0) {
            ans += bfs(i);
        }
    }

    if (ans > K) {
        cout << "Oh no";
    }
    else {
        cout << ans;
    }
    return 0;
}