BOJ 16562

06 Mar 2020 • ProblemSolving

친구비

문제출처

문제 해석

  • N명의 학생과 친구가 되기 위해 필요한 최소 비용을 구하는 문제입니다.
  • “친구의 친구는 친구다”를 이용하여 한 친구에게 돈을 주면 해당 친구의 친구들과 모두 친구가 됩니다.
  • N,M <= 10,000

설계(10)

  • 모든 사람에 대해 bfs탐색을 하여 최소값을 갱신하게 되면 어떻게 될지 생각해보았습니다.
  • 모든 사람을 검사하는데 O(N)의 시간복잡도가 드는데, 모든 정점을 한번만 방문하면 되므로 전체적으로 따져봐도 O(N)의 시간복잡도밖에 걸리지 않음을 알 수 있습니다.
  • 다른 분들은 대체적으로 union-find 기법을 이용하여 문제를 해결하였습니다.
  • 친구관계의 입력을 받는 동시에 union-find기법을 이용하여 비용에 따라 부모-자식관계를 형성시켜 최상위노드의 비용을 모두 더해주는 식으로 구현하였습니다.

구현(10)

코드1 (bfs)
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define MAXN 10001

vector<int> adj[MAXN];
int cost[MAXN];
bool visited[MAXN];
int ans;

int N,M,K;
int bfs(int idx){
    queue<int> q;
    q.push(idx);
    visited[idx] = true;
    int sum = cost[idx];
    while (!q.empty()){
        int cur = q.front();
        q.pop();
        for (int i = 0;i < adj[cur].size(); i++){
            int next = adj[cur][i];
            if (visited[next]) continue;
            visited[next] = true;
            if (sum > cost[next]) sum = cost[next];
            q.push(next);
        }
    }
    return sum;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M >> K;
    for (int i =1; i <= N; i++){
        cin >> cost[i];
    }
    while (M--){
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= N; i++){
        if (!visited[i]){
            ans += bfs(i);
        }
    }
    if (ans <= K) cout << ans <<"\n";
    else cout << "Oh no\n";
    return 0;
}
코드2 (union-find)
#include <iostream>
using namespace std;
#define MAXN 10001

int cost[MAXN];
int parent[MAXN];
int ans;

int N,M,K;
int find(int x){
    if (parent[x] < 0) return x;
    return parent[x] = find(parent[x]);
}
void merge(int u, int v){
    u = find(u);
    v = find(v);
    if (u == v) return;
    if (cost[u] < cost[v]) parent[v] = u;
    else parent[u] = v;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M >> K;
    for (int i =1; i <= N; i++){
        cin >> cost[i];
        parent[i] = -1;
    }
    while (M--){
        int u,v;
        cin >> u >> v;
        merge(u,v);
    }
    for (int i = 1; i <= N; i++){
        if (parent[i]==-1){
            ans += cost[i];
        }
    }
    if (ans <= K) cout << ans <<"\n";
    else cout << "Oh no\n";
    return 0;
}
디버깅
제출결과
  • 4ms

마무리

  • 단순 그래프 탐색 문제였습니다. union-find기법으로 풀 수도 있는 문제였지만 생각을 하지 못했습니다.
 BOJ

Related Posts