[구름 먼데이 챌린지] 카드 교환하기

문제 내용

1부터 N까지의 번호를 가진 N명의 사람이 있다. 각 사람들은 1부터 N 사이의 임의의 수 Ci가 쓰여있는 카드를 한 장씩 가지고 있다.

사람들 간에는 총 M쌍의 친구 관계가 있다. 모든 친구 관계는 양방향이라서, a번 사람과 b번 사람이 친구라면 b번 사람과 a번 사람도 친구이다.

서로 친구 관계에 있는 두 사람끼리는 서로 들고 있는 카드를 원하는 만큼 교환할 수 있다. 모든 사람들은 각자가 들고 있는 카드에 적힌 수가 자신의 번호와 최대한 비슷하기를 원한다. 어떤 한 사람의 불만족도를 그 사람이 들고 있는 카드에 적힌 수와 그 사람의 번호와의 차이로 정의하고, 전체 불만족도는 모든 사람의 불만족도의 합으로 정의한다.

카드 교환이 적절하게 이루어졌을 때, 가능한 전체 불만족도의 최솟값을 구하라.

 

해결 방안

친구 관계간에는 서로 양방향이라는 점에서 여러 친구끼리 묶여서 그룹화가 생길 수 있다. 그래서 union-find로 각각 그룹화시켰다. 여기서 현재 자신의 번호와 카드가 비슷해야한다는점에서 어려움을 느꼇는데 힌트를 찾아본 결과 그룹화된 곳에서 각 사람의 번호와 카드의 번호가 정렬된 경우가 최적의 경우로 해결할 수 있었다.

 

1. 먼저 union-find로 그룹화를 한다.
2. 사람번호와 카드의 점수를 정렬한다.
3. 사람번호와 카드의 점수를 뺀 값들을 구한다.

자바스크립트 코드

// Run by Node.js
const readline = require('readline');

let rl = readline.createInterface({ input: process.stdin });

let input = [];

rl.on('line', (l) => {
	input.push(l);
}).on('close', () => {
	const [n,m] = input[0].split(" ").map(Number);
	
	const c = input[1].split(" ").map(Number);
	let parent = Array.from({length:n}, (_,i) => i);
	
	let graph = {};
	
	let ans = 0;
	
	function find(x) {
		if(parent[x] !== x) {
			parent[x] = find(parent[x]);
		}
		
		return parent[x];
	}
 	
	function union(a,b) {
		a = find(a);
		b = find(b);
		
		if(a > b) {
			parent[a] = b;
		} else {
			parent[b] = a;
		}
	}
		
	for(let i = 2; i< input.length; ++i) {
		const [start,end] = input[i].split(" ").map(Number);
		union(start-1,end-1);
	}
	
	for(let i = 0; i < n; ++i) {
		let p = find(i);
		if(graph[p]){
			graph[p][0].push(i + 1);
			graph[p][1].push(c[i]);
		} else {
			graph[p] = [[i+1],[c[i]]];	
		}
	}
	
	for(let v of Object.values(graph)) {
		const [p, c] = v;
		
		p.sort((a,b) => a-b);
		c.sort((a,b) => a-b);
		
		for(let i = 0; i< p.length; ++i) {
			ans += Math.abs(c[i] - p[i]);
		}
	}
	
	console.log(ans);
})