[구름톤 챌린지] 통신망 분석

풀이 과정

먼저, 이 문제를 풀 때 컴포넌트에 포함된 컴퓨터의 번호를 오름차순으로 공백을 두고 출력하라는 것을 보고, TreeSet 자료구조를 이용하면 좋지 않을까 생각했다. 그래서 나는 컴포넌트들을 TreeSet에 담아두고 밀도들을 비교해서 조건에 맞는 TreeSet을 업데이트하는 방식으로 문제를 풀었다.

 

Static 변수

static ArrayList<Integer>[] A; // 노드와 연결된 노드들의 정보를 담기 위한 배열
static TreeSet<Integer> treeSet; // 나중에 가장 조건에 적합한 컴포넌트
static boolean visited[]; // 방문한 적이 있는지 확인하는 배열
static int indegree[]; // 아래에서 설명
static int totalOrigin = 0; // 컴포넌트의 통신 회선의 개수 * 2

여기서 통신 회선의 개수를 구해야 하는데 하나의 컴포넌트에서 노드들 자신을 가리키는 간선의 개수 정보를 담으면 좋지 않을까 생각해서 진입 차수 indegree를 사용했다. 

예를 들어 예시 1번을 봤을 때 위처럼 하나의 컴포넌트가 구성되는데 2의 진입 차수는 1, 4의 진입 차수는 2, 6의 진입 차수는 1이기 때문에 이를 모두 더하면 4이고, 2로 나누면 통신 회선의 개수가 된다. 근데 나는 밀도를 구하는 것이기 때문에 굳이 2로 나눌 필요는 없다고 생각해서 나누지는 않았다.

 

초기화

for (int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());
    int start = Integer.parseInt(st.nextToken());
    int end = Integer.parseInt(st.nextToken());

    A[start].add(end);
    A[end].add(start);

    indegree[start]++;
    indegree[end]++;
}

위 코드처럼 초기화를 진행하면서 indegree 각 컴퓨터의 진입 차수를 구하도록 만들었다.

 

컴퓨터 순회

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

컴퓨터들을 순회하면서 이미 방문한 적이 있으면 이미 하나의 컴포넌트를 순회한 것이기 때문에 방문한 적이 없는 컴퓨터만 방문할 수 있도록 분기문 처리를 했다.

 

BFS

public static void bfs(int node) {
    TreeSet<Integer> tempSet = new TreeSet<>();
    Queue<Integer> queue = new LinkedList<>();
    visited[node] = true;
    tempSet.add(node);
    queue.offer(node);

    int totalTemp = 0;

    while (!queue.isEmpty()) {
        int now = queue.poll();
        totalTemp += indegree[now];

        for (int next : A[now]) {
            if (!visited[next]) {
                visited[next] = true;
                tempSet.add(next);
                queue.offer(next);
            }
        }
    }

    if (treeSet.size() == 0) {
        treeSet = tempSet;
        totalOrigin = totalTemp;
        return;
    }

    double tempRatio = (double) totalTemp / tempSet.size();
    double originRatio = (double) totalOrigin / treeSet.size();

    if (tempRatio < originRatio) { // 새로 구한 밀도가 작으면
        return;
    }

    if (tempRatio == originRatio && tempSet.size() > treeSet.size()) {
        return;
    }

    if (tempRatio == originRatio && tempSet.size() == treeSet.size() && tempSet.first() > treeSet.first()) {
        return;
    }

    treeSet = tempSet;
    totalOrigin = totalTemp;
}

BFS() 메서드가 가장 긴데 하나의 컴포넌트를 구성할 TreeSet을 정의하고, BFS하기 위한 Queue를 정의했다. 그리고 해당 컴퓨터를 방문했기 때문에 visited[node] = true;로 방문했다고 정보를 남기고, TreeSet, Queue 각각 해당 컴퓨터를 담는다.

Queue가 빌 때까지 루프를 돌면서 Queue에 가장 먼저 들어온 컴퓨터를 꺼내 totalTemp에 해당 컴퓨터의 진입 차수를 더한다. 그리고 해당 컴퓨터와 인접한 컴퓨터들을 돌면서 방문한 적이 없으면 이제 방문할 것이기 때문에 visited[true]; 그리고 TreeSet, Queue 객체에 각각 담는다.

이렇게 하나의 컴포넌트를 모두 순회하면 루프를 빠져나와 만약 우리의 결과가 될 treeSet 객체가 아직 size가 0이라면 처음 컴포넌트를 순회한 것이기 때문에 해당 TreeSet 객체로 업데이트해주고, 아니라면 아래 조건들을 분기 처리를 통해 걸려줬다.

문제에서 보는 조건은 다음과 같다.

1. 가장 밀도가 높은 컴포넌트를 출력한다.
2. 1을 만족하는 컴포넌트가 여러 개라면, 컴포넌트를 구성하는 컴퓨터의 수가 가장 작은 컴포넌트를 출력한다.
3. 2를 만족하는 컴포넌트가 여러 개라면, 더 작은 번호를 가진 컴퓨터가 있는 컴포넌트를 출력한다.

나는 위 조건들을 반대로 생각해서 분기 처리를 했다.

if (tempRatio < originRatio) { // 새로 구한 밀도가 작으면
    return;
}

if (tempRatio == originRatio && tempSet.size() > treeSet.size()) {
    return;
}

if (tempRatio == originRatio && tempSet.size() == treeSet.size() && tempSet.first() > treeSet.first()) {
    return;
}

먼저, 1번 가장 밀도가 높은 컴포넌트를 출력해야 하기 때문에 다음 컴포넌트가 이전 컴포넌트보다 밀도가 작으면 업데이트 하지 않고, 2번 만약 밀도가 같은데 다음 컴포넌트가 이전 컴포넌트보다 컴퓨터의 수가 크면 업데이트하지 않는다. 그리고 마지막 3번도 밀도도 같고 컴퓨터의 수도 같은데 이전 컴포넌트의 가장 작은 번호가 다음 컴포넌트의 가장 작은 번호보다 작다면 업데이트하지 않도록 분기처리를 했다.

 

만약 위 분기문을 모두 통과했다면 기존에 있는 컴포넌트보다 더 조건에 맞는 컴포넌트이기 때문에 업데이트를 해줘 가장 조건에 맞는 컴포넌트를 찾아 마지막에 출력해줄 수 있도록 하여 문제를 통과할 수 있었다.

 

코드

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

class Main {
	
	static ArrayList<Integer>[] A;
	static TreeSet<Integer> treeSet;
	static boolean visited[];
	static int indegree[];
	static int totalOrigin = 0;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		A = new ArrayList[N + 1];
		visited = new boolean[N + 1];
		indegree = new int[N + 1];
		treeSet = new TreeSet<>();
		
		// 초기화
		for (int i = 0; i <= N; i++) {
			A[i] = new ArrayList<>();
		}
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			
			A[start].add(end);
			A[end].add(start);
			
			indegree[start]++;
			indegree[end]++;
		}
		
		for (int i = 1; i <= N; i++) {
			if (!visited[i]) {
				bfs(i);
			}
		}
		
		for (int node : treeSet) {
			System.out.print(node + " ");
		}
	}
	
	public static void bfs(int node) {
		TreeSet<Integer> tempSet = new TreeSet<>();
		Queue<Integer> queue = new LinkedList<>();
		visited[node] = true;
		tempSet.add(node);
		queue.offer(node);
		
		int totalTemp = 0;
		
		while (!queue.isEmpty()) {
			int now = queue.poll();
			totalTemp += indegree[now];
			
			for (int next : A[now]) {
				if (!visited[next]) {
					visited[next] = true;
					tempSet.add(next);
					queue.offer(next);
				}
			}
		}
		
		if (treeSet.size() == 0) {
			treeSet = tempSet;
			totalOrigin = totalTemp;
			return;
		}
		
		double tempRatio = (double) totalTemp / tempSet.size();
		double originRatio = (double) totalOrigin / treeSet.size();
		
		if (tempRatio < originRatio) { // 새로 구한 밀도가 작으면
			return;
		}
		
		if (tempRatio == originRatio && tempSet.size() > treeSet.size()) {
			return;
		}
		
		if (tempRatio == originRatio && tempSet.size() == treeSet.size() && tempSet.first() > treeSet.first()) {
			return;
		}
		
		treeSet = tempSet;
		totalOrigin = totalTemp;
	}
}