[구름톤 챌린지] 4주차_통신망 분석

 

필요한 개념

---

• 그래프
• BFS / DFS

 

 

문제 분석

---

그래프 탐색을 통해 다양한 정보를 얻어서 처리해야 하는 문제이다.

문제의 요구 조건을 만족하는 컴포넌트를 찾기 위해서는 다음 세가지를 찾아야 한다.

1. 컴포넌트에 속한 컴퓨터의 수
2. 컴포넌트에 속한 통신 회선의 수
3. 컴포넌트에서 가장 작은 컴퓨터의 번호

세 정보를 잘 이용해 조건에 맞는 컴포넌트를 출력하면 된다.

 

 

컴포넌트

---

그래프 이론에서 컴포넌트는 보통 연결된 부분 그래프를 의미한다.

그 중에서 연결 컴포넌트의 개념이 있다.

그래프는 여러 개의 연결 컴포넌트로 나누어질 수 있으며, 하나의 연결 컴포넌트는 그 그래프 내의 모든 정점들이 경로를 통해 서로 연결될 수 있는 정점의 집합이다.

그래프의 각 연결 컴포넌트는 다른 연결 컴포넌트의 정점과는 직접적인 경로가 없다.

연결 컴포넌트는 그래프 내에서 서로 연결된 정점들의 집합을 말한다.

 

 

그래프 탐색으로 필요한 정보 얻기

---

..code 데이터 입력 코드
let start = 1;
const visited = new Array(N + 1).fill(false);
if (!visited[start]) {
	// 방문한 적 없을 때 탐색
	const q = [start];
	const component = new Set();
	// start 노드에서 출발했을 때, 
	// 포함될 수 있는 모든 컴포넌트 확인
	while (q.length > 0) {
		const now = q.pop();
		if (!visited[now]){
			visited[now] = true;
			component.add(now);
			if (graph[now]){
				for (const to of graph[now]) {
					if (!visited[to]) {
						q.push(to);
					}
				}
			}
		}
	}
}

component 집합에 start 에서 시작해 도달한 컴퓨터들이 모두 저장되어 있다.

필요한 세가지 정보 중에서 컴퓨터의 수는 len(component) 로 구하고, 가장 작은 컴퓨터의 번호는 component 를 리스트로 변환하고 정렬한 첫 번째 값이다.

마지막으로 컴포넌트 내부에 통신 회선이 몇 개가 있는지만 찾으면 된다.

 

// 간선의 수를 저장할 변수 선언
let edge = 0;

// 컴포넌트에 속한 모든 컴퓨터에 대해서 순회
for (const j of component) {
	// 범위 오류 방지를 위해서, 간선이 존재하는 노드인지 확인
	if (graph[j]){
		// 도달 가능한 컴퓨터 중에서, 
		for (const to of graph[j]) {
			// 해당 컴포넌트에 속한다면 컴포넌트 내부의 통신 회선
			if (component.has(to)) {
				edge += 1;
			}
		}
	}
}

component 를 집합으로 선언했던 이유는 바로 이 부분 때문이다.

간선의 존재 여부를 확인하기 위해서, 집합은 상수 시간이 걸린다.

 

마지막으로 출력해야 하는 값은 조건을 만족하는 컴포넌트에 포함된 컴퓨터의 번호들이므로, component 배열이 필요하다.

추가로, 컴포넌트끼리 비교할 때 밀도가 필요하다.

const tempDensity = edge / component.size;

 

 

요구 조건 판별

---

먼저 답을 저장할 변수들을 선언한 다음, 탐색을 진행하며 값들을 업데이트 해준다.

const result = [];
let density = 0;
for (let i = 1; i <= N; i++) {
		// 방문하지 않은 컴퓨터인 경우만 탐색
		if (!visited[i]) {
			..code
		}
}

 

result, density 와 temp, tempDensity 를 비교하며 답을 구한다.

조건을 순서대로 사용하면 실수값 오차가 생길 수 있다.

BFS 함수에서 반환하는 edge / len(component) 의 값이 실수이기 때문에 문제가 발생할 수 있다.

따라서 대소 비교를 하기 전에 density 와 tempDensity 가 같은 값인지 확인한다.

if (Math.abs(tempDensity - density) < 1e-8) {
		// 만약에 밀도가 같으면, 2번 조건 확인
		// 만약 현재 컴포넌트 배열이 더 크면 result 값 확인
		// 만약에 배열의 크기가 같으면 첫번째 값 비교
		if (component.size > result.length || (component.size === result.length && i < result[0])) {
			result.length = 0;
			Array.prototype.push.apply(result, Array.from(component));
			density = tempDensity;
		}
	} 
// 밀도가 다른 경우 1번 조건 고려
else if (tempDensity > density) {
		result.length = 0;
		Array.prototype.push.apply(result, Array.from(component));
		density = tempDensity;
}

 

이와같이 조건을 따져 비교하면 답을 구할 수 있다.

조건을 만족하는 컴포넌트를 오름차순으로 정렬해서 출력한다.

result.sort((a, b) => a - b);
console.log(result.join(' '));

 

 

그래프와 BFS, DFS 탐색 문제를 막힘 없이 푸는 그날까지.. 화이팅!