[BOJ/C++] 1922: 네트워크 연결

🏅 Gold 4

✏️ 1차 솔루션

⭐️ 크루스칼 알고리즘 사용

1. 비용을 기준으로 오름차순 정렬
   ➡️ 출발 컴퓨터, 도착 컴퓨터, 비용을 struct 로 구성하여 vector 에 저장한 후 sort
2. 컴퓨터 연결할 때마다 root 컴퓨터를 표시해줘서 어디까지 연결되었는지 파악 가능하도록 함
   ➡️ visit 여부를 vector 로 관리하는데 초기에는 visit 값을 자기 자신으로 초기화
   ➡️ 컴퓨터 연결할 때 visit 값을 root 컴퓨터로 갱신하기 위해 재귀함수로 visit 값이 자기 자신일 때까지 타고 가서 root 컴퓨터 값을 return 하도록 함
   ➡️ 도착 컴퓨터나 출발 컴퓨터 둘 중 하나의 visit 값이 자기 자신이라면, 해당 컴퓨터의 visit 값을 상대 컴퓨터의 root 컴퓨터 값으로 갱신

• 사이클을 방지하기 위해 출발 컴퓨터와 도착 컴퓨터가 이미 연결되어 있으면 컴퓨터 연결 skip ➡️ root 컴퓨터가 같은 경우
• 간선을 지날 때마다 count해서 모든 컴퓨터가 연결되었을 때 break

🚨 1차 trouble

자꾸 틀렸다고 뜬다ㅠㅠ
연결된 컴퓨터 개수 count 하는 기준이 잘못된 것 같음.

✏️ 최종 솔루션

원래는 visit vector 만 갱신해주던 부분을 부모 가져오기, 합집합 만들기, 부모 같은지 확인하는 함수를 만들어서 합집합 만들어가는 과정을 세분화해서 체킹

1. 부모 가져오기 함수
   node의 부모가 자기 자신이라면 루트 노드라고 판단해 node return
   이외의 경우는 계속해서 루트 노드를 탐색하기 위해 node 의 현재 부모 노드를 재귀로 넣고 return 값을 현재 부모 노드로 갱신
2. 합집합 함수
   a와 b의 부모 노드가 다르다면 합집합을 만들어야 하므로 a나 b의 부모 노드를 b 의 부모 노드로 갱신
3. 같은 부모인지 확인하는 함수: 단순히 부모 같으면 true, 아니면 false

📌 self feedback

어차피 정답은 나오는데 왜 틀렸다고 하는지 모르겠음
struct 로 출발 노드, 도착 노드, 가중치를 한번에 저장하는 것은 pair 보다 복잡하지 않고 깔끔한 방법인 것 같음
부모가 같은지 확인하고 부모가 같지 않다면
부모가 같은 경우, skip 되기 때문에 별도 예외처리없이 사이클 방지 가능
모든 컴퓨터를 연결했을 경우에 대한 처리는 굳이 안해줘도 상관없음

✏️ 최종 code

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

struct com {
    int a;    //출발 컴퓨터
    int b;    // 도착 컴퓨터
    int c;    //비용
};

bool cmp(com &x, com&y) {
    if(x.c==y.c) return x.a<y.a;
    
    return x.c<y.c;
}

vector<int> visit;

// 부모 가져오기
int getParent(int node) {
    if(visit[node]==node) return node;
    else return visit[node]=getParent(visit[node]);
}

// 합집합
void unionParent(int a, int b) {
    a=getParent(a);
    b=getParent(b);
    
    if (a!=b) visit[a]=b;
}

// 부모 같은지 확인
bool findParent(int a, int b) {
    if (getParent(a)==getParent(b)) return true;
    else return false;
}

int main() {
    int n, m,a,b,c;
    cin >> n >> m;
    
    vector<com> v;
    for(int i=0;i<m;i++) {
        cin >> a>> b>>c;
        
        v.push_back({a,b,c});
    }
    
    sort(v.begin(),v.end(),cmp);

    visit.push_back(-1);
    for (int i=1; i<=n; i++) {
        visit.push_back(i);
    }
    
    int ans=0;
    for(int i=0;i<v.size();i++) {
        a=v[i].a;
        b=v[i].b;
        c=v[i].c;
        
        // 부모가 다를 경우 합집합으로 묶어주기 -> 이외의 경우는 이미 합집합이므로 사이클 피하기 위해 skip
        if (!findParent(a, b)) {
            ans+=c;
            unionParent(a, b);
        }
           
    }

    cout << ans << endl;

}