1922: 네트워크 연결

[minsoo0715]

1922: 네트워크 연결

소스 코드

아이디어

Greedy의 일종인 prim 알고리즘을 통해 최소 스패닝 트리를 찾는다.

구현

connected[1] = true; // 1번 노드부터 시작
while(true) {
    int min = 10001;
    int k = -1, l = -1;
    for(int i = 0; i<edges.size(); ++i) {
        pair<int, int> e = edges[i];
        if(!connected[e.first] && !connected[e.second]) continue; // 두 노드 중 연결된 노드가 하나도 없는 경우
        if(connected[e.first] && connected[e.second]) continue; // 두 노드가 이미 최소 스패닝 트리에 포함되어 있는 경우 (루프 발생 가능)
        if(costs[i] < min) { // 최소값 업데이트
            min = costs[i];
            k = e.first;
            l = e.second;
        }
    }

    if(min == 10001) break; // 아무 노드도 선택되지 않은 경우 = 모든 노드가 연결된 경우
    ans += min;
    connected[k] = true;
    connected[l] = true;
}