구름톤 챌린지 4주 차 학습 일기

구름톤 챌린지란?

구름 이라는 곳에서 문제 풀이 챌린지(구름톤 챌린지)를 한다고 해서 참여 중이다. 이벤트 기간 동안 문제가 꾸준이 올라오며, 주에 2회씩 (혹은 그 이상) 챌린지 문제들에 대해 풀이가 가능한 문제들을 풀이해보고, 후기를 남겨보려고 한다.

문제 푸는 곳: https://level.goorm.io/l/challenge/goormthon-challenge
학습 일기 작성 가이드: https://goorm.notion.site/5ad9e8eef00f4c19b083572c2000d7f8
풀이 사용 컨테이너(구름 컨테이너): https://goor.me/8jsC9vbx5TCeaCcRA

문제 풀이

문제 제목: 통신망 분석
문제 링크: https://level.goorm.io/exam/195699/%EA%B7%B8%EB%9E%98%ED%94%84%EC%9D%98-%EB%B0%80%EC%A7%91%EB%8F%84/quiz/1
문제 예상 티어: Gold V

풀이 접근

어제와 마찬가지로 나의 경우 Union Find로 접근했다. 같은 집합에 속하는 녀석들을 관리할 때는 이 방법이 제일 편하다.

풀이 과정은 아래와 같다.

입력을 받으면서 같은 집합에 속하는 애들을 merge 한다
다시 처음부터 정점을 순회하면서 root를 확인해서, 처음 나오는 root 면 Component를 생성한다.
- 현재 정점이 속한 Component에 해당 컴퓨터를 추가한다.
Component 안에 속하는 컴퓨터들이 가진 간선의 갯수를 세서 반영한다.
문제에서 준 기준으로 Component를 정렬한다.
0번째 index의 Component의 원소들을 출력한다.

그래프를 다루는 법만 잘 알고 있다면 순수 구현 문제처럼 풀이가 된다.

주의해야할 점은 정렬할 때 인데, 밀도의 계산을 분수로 하게 되면 WA를 받기 쉽다. 이 경우 분수로 하기보다는 $a / b$ 와 $c / d$ 를 비교한다 할 때 $a * d$ 와 $b * c$ 를 비교하는 식으로 회피하면 실수 오차 없이 정렬할 수 있다. 또, 이 경우 문제 조건에서 수의 범위가 int 범위를 초과할 수 있으므로, long long을 사용해야 한다. (Worst 시 $10^5 \times 2*10^5 = 2*10^{10}$ > 0x7FFFFFFF 이다)

시간 복잡도의 병목 부분은 정렬과 처음 간선 입력을 받는 부분이고, $O(M + N \log N)$ 이다.

내 풀이

#include <bits/stdc++.h>
using namespace std;

int N, M;
typedef long long ll;
struct UF {
    int parent[100001];
    UF() {
        for(int i = 0; i <= 100000; ++i) parent[i] = i;
    }
    int getRoot(int v) {
        if (v == parent[v]) return v;
        return parent[v] = getRoot(parent[v]);
    }
    void merge(int a, int b) {
        a = getRoot(a);
        b = getRoot(b);
        if (a == b) return;
        parent[b] = a;
    }
} uf;

vector<int> adj[100001];

struct Component {
    ll numComputer;
    ll numConnection;
    vector<int> members;

    bool operator<(const Component& t) const {
        // 1. 커넥션 수 / 컴퓨터 수
        // 2. 밀도 같으면 컴퓨터 적은 수
        // 3. 더 작은 번호 컴퓨터 순
        if (numComputer * t.numConnection != numConnection * t.numComputer) {
            return numComputer * t.numConnection < numConnection * t.numComputer;
        }
        if (numComputer != t.numComputer) {
            return numComputer < t.numComputer;
        }
        return members[0] < t.members[0];
    }
} com[100000];

int main() {
    scanf("%d %d", &N, &M);

    for(int i = 0; i < M; ++i) {
        int a, b; scanf("%d %d", &a, &b);
        adj[a].push_back(b);
        uf.merge(a, b);
    }

    int cid = 0;
    map<int, int> uq;
    for(int a = 1; a <= N; ++a) {
        if (uq.find(uf.getRoot(a)) == uq.end()) {
            uq[uf.getRoot(a)] = cid;
            ++cid;    
        }
        int gid = uq[uf.getRoot(a)];
        com[gid].members.push_back(a);
        com[gid].numComputer++;
    }
    for(int c = 0; c < cid; ++c) {
        ll cnt = 0;
        for(auto& cur: com[c].members) {
            cnt += adj[cur].size();
        }
        com[c].numConnection = cnt;
    }
    sort(com, com + cid);

    for(auto& item: com[0].members) {
        printf("%d ", item);
    }
    printf("\n");
    return 0;
}