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

문제

---

이 세상에는 수많은 컴퓨터들이 통신망을 통해 서로 연결되어 정보를 교류하고 있다. 오늘 플레이어는 이 거대한 통신망 중 한 구역을 조사하고자 한다.

플레이어가 조사할 구역에는 $N$개의 컴퓨터가 있고, $M$개의 통신 회선이 있다. 각 컴퓨터는 $1$번부터 $N$번까지 번호가 붙어 있고, 통신 회선은 서로 다른 두 컴퓨터를 양방향으로 연결하고 있다.

컴퓨터들은 연결 여부에 따라 여러 개의 컴포넌트로 나뉜다. 어떤 두 컴퓨터가 통신 회선만을 이용해서 연결되어 있다면 두 컴퓨터는 같은 컴포넌트에 속한다.

플레이어는 여러 개의 컴포넌트 중, 가장 밀도가 높은 컴포넌트를 조사하려고 한다. 컴포넌트의 밀도는 그 컴포넌트에 포함된 통신 회선의 개수를 컴퓨터의 수로 나눈 값이다. 주어진 통신 구역을 분석해서, 가장 밀도가 높은 컴포넌트의 정보를 출력해보자.

입력

---

첫째 줄에 컴퓨터의 개수 $N$과 통신 회선의 개수 $M$이 공백을 두고 주어진다.
다음 $M$개의 줄에는 통신 회선이 잇는 두 정점 $a_i, b_i$가 공백을 두고 주어진다.

 

 

• $2 \leq N \leq 100 \ 000$
• $1 \leq M \leq 200 \ 000$
• $1 \leq a_i, b_i \leq N; a_i \neq b_i$
• 같은 두 컴퓨터 쌍을 연결하는 통신 회선은 최대 하나이다.
• 입력에서 주어지는 모든 수는 정수이다.

출력

---

아래 조건을 만족하는 컴포넌트에 포함된 컴퓨터의 번호를 오름차순으로 공백을 두고 출력한다.

 

 

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

---

문제 접근 방식

---

나의 경우 BFS를 이용해서 연결 요소를 판단했다.

 

그래프의 밀집도를 확인하기 위해, 우리는 컴포넌트에 있는 간선의 개수를 세어줄 필요가 있다.

 

간선의 개수를 직접 센 것이 아닌, Handshaking Lemma를 사용하여 간선의 개수를 세어주었다.

 

Handshaking Lemma란, 모든 정점의 차수(Degree)를 더하면 한 그래프의 간선의 개수의 두 배가 된다는 정리이다.

 

BFS를 돌려서 주변 노드를 확인할 때마다, 우리는 그 정점의 차수를 구할 수 있으므로 한 컴포넌트에 속한 모든 정점의 차수의 합을 구할 수 있다.

 

그 합에 절반을 취해주면 간선의 개수를 구할 수 있다.

 

또한, BFS를 돌릴 때마다 그 컴포넌트에는 실제로 어떤 요소가 있는지를 저장하는 빈 리스트를 선언하고 탐색할 때마다 그 리스트에 탐색하는 요소들을 저장해주었다.

 

우리는 오름차순으로 정렬된 컴포넌트를 출력하기 원하므로, 한 노드에 대해서 BFS탐색이 끝나면 그 컴포넌트 리스트를 정렬해주었다.

 

이후 출력에서 원하는 바대로, 가장 밀도가 높고, 구성하는 컴퓨터의 수가 적으며, 더 작은 번호를 가지는 컴포넌트를 출력하도록 컴포넌트를 갱신해가며 따져주었다.

 

---

정답 코드

---

# 통신망 분석
import sys
input = sys.stdin.readline
from collections import deque

N, M = map(int, input().rstrip().split())
graph = [[] for _ in range(N+1)]
visited = [0 for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().rstrip().split())
    graph[u].append(v)
    graph[v].append(u)

def BFS(node):
    queue = deque()
    queue.append(node)
    visited[node] = 1
    component = []
    component.append(node)
    # sum_degree//2 = sum_edges
    total_degree = 0
    while queue:
        node = queue.pop()
        for near_node in graph[node]:
            total_degree += 1
            if visited[near_node] == 0:
                visited[near_node] = 1
                queue.append(near_node)
                component.append(near_node)
    component.sort()
    return component, (total_degree//2)/len(component)

max_density = 0
max_component = []

for node in range(1, N+1):
    if visited[node] == 0:
        component, density = BFS(node)
        if density > max_density:
            max_density = density
            max_component = component
        elif density == max_density:
            if len(component) < len(max_component):
                max_component = component
            elif len(component) == len(max_component):
                if component[0] < max_component[0]:
                    max_component = component

print(*max_component)

 

---

특별히 배운 점

---

Handshaking Lemma를 복습할 수 있는 기회여서 좋은 문제였다.