[구름톤 챌린지] 4-2. 통신망 분석

코드

import java.io.*;
import java.util.*;

public class Main {

    static int n, m;
    static ArrayList<Integer>[] graph;
    static boolean[] visited;

    static class Component implements Comparable {
        PriorityQueue<Integer> nodes;
        int cnt;
        double density;

        public Component() {
            this.nodes = new PriorityQueue<>(Comparator.comparing(o -> o));
            this.cnt = 0;
            this.density = 0.0;
        }

        @Override
        public int compareTo(Object o) {
            Component component = (Component) o;
            if (component.density != this.density) {
                if (component.density > this.density) return 1;
                else return -1;
            }
            else if (component.nodes.size() != this.nodes.size()) return this.nodes.size() - component.nodes.size();
            else return this.nodes.peek() - component.nodes.peek();
        }
    }

    static ArrayList<Component> components = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        n = line[0]; m = line[1];
        graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            graph[line[0]].add(line[1]);
            graph[line[1]].add(line[0]);
        }
        visited = new boolean[n + 1];

        for (int i = 1; i <= n; i++) {
            if (!visited[i])
                bfs(i);
        }

        Collections.sort(components);
			
        while(!components.get(0).nodes.isEmpty()) bw.write(components.get(0).nodes.poll() + " ");
        bw.flush();
    }

    private static void bfs(int start) {
        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(start);
        Component component = new Component();

        while (!queue.isEmpty()) {
            Integer poll = queue.poll();

            if (!visited[poll]) {
                visited[poll] = true;
                component.nodes.add(poll);

                for (Integer integer : graph[poll]) {
                    component.cnt++;
                    queue.add(integer);
                }
            }
        }
        component.cnt /= 2;
        component.density = (double) component.cnt / component.nodes.size();

        components.add(component);
    }
}

코드 설명

이 문제는 두 가지 단계로 나눌 수 있다.

1. 컴포넌트를 찾는다.
2. 찾은 컴포넌트들끼리 비교한다.

 

1. 컴포넌트 찾기

컴퓨터라는 특정 정점은 다른 컴퓨터와 통신 회선이라는 간선으로 연결되며, 연결된 컴퓨터들을 한 컴포넌트에 속한 것으로 간주한다.

이 때 통신 회선은 양방향이므로 입력을 받을 때 인접 그래프에 양쪽 모두 추가해 주어야 한다.

 

컴포넌트는 bfs, dfs를 모두 사용할 수 있지만 조금 더 익숙한 bfs를 사용했다.

 

또한 컴포넌트는 클래스를 이용해서 쉽게 관리했다.

static class Component {
    PriorityQueue<Integer> nodes;
    int cnt;
    double density;
}

멤버 함수와 비교 함수를 제외한 Component 클래스이다.

1) PriorityQueue<Integer> nodes : 컴포넌트에 속한 컴퓨터들을 우선순위 큐로 저장

2) int cnt : 통신 회선의 개수

3) double density : 밀도

 

bfs를 특정 정점에서 수행할 경우, 그 정점을 기준으로 하나의 컴포넌트가 만들어지게 된다.

탐색을 할 때, 이전에 탐색된 적이 없는 정점일 경우 visited를 체크해주어 컴포넌트에 중복으로 들어가는 일이 없도록 만들었다.

for (int i = 1; i <= n; i++) {
    if (!visited[i])
        bfs(i);
}

private static void bfs(int start) {
    LinkedList<Integer> queue = new LinkedList<>();
    queue.add(start);
    Component component = new Component();

    while (!queue.isEmpty()) {
        Integer poll = queue.poll();

        if (!visited[poll]) {
            visited[poll] = true;
            component.nodes.add(poll);

            for (Integer integer : graph[poll]) {
                component.cnt++;
                queue.add(integer);
            }
        }
    }
    component.cnt /= 2;
    component.density = (double) component.cnt / component.nodes.size();

    components.add(component);
}

하나의 정점을 탐색할 때 연결된 통신 회선의 개수를 모두 더해주었다. (cnt++)

이 때, 통신 회선은 양방향이기 때문에 간선에 대한 중복 체크를 하지 않았을 경우 하나의 통신 회선에 두 번 cnt가 측정되게 된다.

따라서 탐색이 종료되면 2로 나누어 주었다.

 

2. 컴포넌트 비교

 

다음은 Component의 implement 함수인 compareTo이다.

@Override
public int compareTo(Object o) {
    Component component = (Component) o;
    if (component.density != this.density) {
        if (component.density > this.density) return 1;
        else return -1;
    }
    else if (component.nodes.size() != this.nodes.size()) return this.nodes.size() - component.nodes.size();
    else return this.nodes.peek() - component.nodes.peek();
}

밀도 -> 컴포넌트에 속한 컴퓨터의 개수 -> 작은 번호를 가진 컴퓨터

순으로 정렬 조건을 정하고 정렬했다.

 

컴포넌트에 속한 컴퓨터들은 우선순위 큐로 오름차순으로 정렬되기 때문에 peek() 함수로 쉽게 컴퓨터 간의 번호를 비교할 수 있다.

---

잘 만들어놓고 컴포넌트 정렬을 안해줘서 처음에 FAIL을 받았다🤔