[C++] vector<T>

vector<Type> examples(M); //M개의 Type객체를 디폴트 생성자로 초기화
-------------------------
vector<Type> examples;
examples.emplace_back(); //이후 추가​

 

1. vector<Type> examples(M);

: 이미 M개의 Type 객체를 디폴트 생성자를 사용하여 초기화 한다

- 디폴트 생성자가 필요함 (명시적 생성자가 없는 경우, 자동생성됨)

- examples.emplace_back()으로 새로운 객체를 추가하는 경우, M개의 초기화된 객체 뒤에 새로운 Type 객체를 추가하는 것임

 

2. vector<Type> examples; examples.emplace_back(); 

: 이후에 emplace_back()을 통해 추가한다

-> 파라미터가 있는 생성자로도 추가할 수 있다

vector<Type> examples;

examples.emplace_back(x,y,weight);

 

---

[예시 코드] - 백준 1922 네트워크 연결

#include <iostream>
#include <vector>
#include <algorithm> //std::sort

#define MAX 1001

using namespace std;

int res = 0;

struct Edge{
    int x,y,weight;
    Edge(int x, int y, int weight) : x(x), y(y), weight(weight){}
};

class DisjointSet{ //분리 집합
private:
    int parent[MAX]; //parent의 index
    int rank[MAX]; //높이를 나타냄

public:
    DisjointSet(int n){ //n은 index번호
        for(int i=1;i<=n;i++){
            parent[i] = i;
            rank[i] = 0;
        } 
    }

    int find(int a){
        if(parent[a]!=a){ //본인이 루트가 아닌 경우
            parent[a] = find(parent[a]); //분리 집합 -> 겁색할 때마다, 부모를 갱신해줌
        }
        return parent[a]; //꼭대기에 도달한 경우
    }

    void unionSet(int a, int b){
        int rootA = find(a);
        int rootB = find(b);

        if(rootA != rootB){
            if(rank[rootA] > rank[rootB]){ //Aset의 rank가 더 클 때
                parent[rootB] = rootA; //Aset에 Bset union
            }else if(rank[rootA] < rank[rootB]){
                parent[rootA] = rootB; 
            }else{
                parent[rootB] = rootA;
                rank[rootA]++;
            }
        }
    }
};

//sort할때 비교에 사용하는 함수
bool compareWeights(const Edge &a, const Edge &b){
    return a.weight < b.weight; //오름차순 정렬
}

int main(){
    int N,M;
    cin >> N >> M;

    vector<Edge> edges;

    for(int i=0;i<M;i++){
        int x, y, weight;
        cin >> x >> y >> weight;
        edges.emplace_back(x,y,weight); //edges에 추가
    }
    sort(edges.begin(), edges.end(),compareWeights); //가중치에 대한 오름 차순으로 정렬

    DisjointSet ds(N); //N개의 노드의 parent, 컴포넌트 정보가 있는 ds

    for(const auto &edge : edges){
        int aRoot = ds.find(edge.x);
        int bRoot = ds.find(edge.y);
        if(aRoot != bRoot){
            res += edge.weight;
            ds.unionSet(aRoot,bRoot);
        }
    }

    cout << res <<endl;
    return 0;
}