구름톤 챌린지 17일차 통신망 분석 [Javascript]

 

그래프문제로 union find로 통해 분리하고 주어진 조건에 정렬하는 문제이다. 

const readline = require('readline');
let rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});
let input = [];
rl.on('line', (line) => {
	input.push(line);
});

rl.on('close', () => {
	let [n,m] = input[0].split(" ").map((v) => parseInt(v));
	
	let parent = Array.from({length:n + 1}, (_,i)=>i);
	let edges =  Array.from({length:n + 1}, ()=> 0);
	
	function find(v) {
		if(parent[v] !== v) parent[v] = find(parent[v]);
		
		return parent[v];
	}
	
	function union(a,b) {
		a = find(a);
		b = find(b);
		
		if(a>b){
			parent[a] = b;
		} else {
			parent[b] = a;
		}
	}
	
	for(let i = 0; i<m; ++i){
		const [a,b] = input[i+1].split(" ").map((v)=>parseInt(v));
		
		edges[a] = edges[a] + 1;
		union(a,b);
	}
	
	const components = {};
	
	for(let i = 1; i<parent.length; ++i) {
		if(components[find(i)]){
			components[find(i)].push(i);
		} else {
			components[find(i)] = [i]
 		}
	}
	
	let groups = [];
	
	for(const group of Object.values(components)){
		  let edgeCount = group.reduce((v,c) => v + edges[c],0)
			
			let density = edgeCount / group.length;
			
			groups.push({
				density: density,
				group: group,
				length: group.length,
				smallestComputer: Math.min(...group)
			})
	}
	
	groups.sort((a,b) => b.density - a.density || a.length - b.length ||a.smallestComputer - b.smallestComputer)
	
	console.log(groups[0].group.join(" "))
})

https://level.goorm.io/l/challenge/goormthon-challenge