[Goorm/Python] 통신망 분석 || 구름톤 챌린지 (union, bfs)

구름톤 챌린지 통신망 분석 파이썬

구름LEVEL

❏ 문제 설명

❍ 문제

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

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

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

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

❍ 예제 설명

첫 번째 예제에서 주어진 통신 구역에는 두 개의 컴포넌트가 있다. 한 컴포넌트는 (1, 3, 5, 7)번 컴퓨터로 이루어져 있고, 다른 컴포넌트는 (2, 4, 6)번 컴포넌트로 이루어져 있다.

(1, 3, 5, 7)번 정점으로 구성된 컴포넌트에는 네 개의 통신 회선이 존재하므로, 이 컴포넌트의 밀도는 $4/4 = 1$이다. (2, 4, 6)번 컴퓨터로 구성된 컴포넌트에는 두 개의 통신 회선이 존재하므로, 이 컴포넌트의 밀도는 $2/3$이다. 먼저 주어진 컴포넌트의 밀도가 더 크므로, 1 3 5 7을 답으로 출력해야 한다.

❍ 입력

첫째 줄에 컴퓨터의 개수 N과 통신 회선의 개수 M이 공백을 두고 주어진다.

다음 M개의 줄에는 통신 회선이 잇는 두 정점 $a_i, b_i$가 공백을 두고 주어진다.

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

❍ 출력

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

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

 

❏ 문제 풀이

union( 합집합 )과 find ( 찾기 ) 를 통해, 서로 속해있는 집합을 찾는 연산을 이용하여 문제를 풀이해보았다.
 
< 서로소 집합 >

[Algorithm/Python] 서로소 집합(Disjoint Sets) 알고리즘이란?

 

❍ union과 find

def find_parent(a):
    if parent[a] != a:
        return find_parent(parent[a])
    else:
        return a

def union(a, b):
    a = find_parent(a)
    b = find_parent(b)

    if a < b:
        parent[a] = b
    else:
        parent[b] = a

서로의 부모를 찾아, 큰 노드를 기준으로 부모 노드를 바꾸어주었다.
 

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
parent = [i for i in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    union(a, b)

u = defaultdict(list)
for i in range(1, n + 1):
    p = find_parent(i)
    u[p] += [i]

따라서, a 노드와 b 노드의 union 연산을 수행 후에, 각 원소가 속한 집합을 defaultdict에 담아 각 부모에 따른 집합을 확인할 수 있도록 하였다.
 

result = []
for values in union.values():
    count = 0
    for j in values:
        count += len(graph[j])
    result.append((count / len(values), len(values), min(values), values))

result.sort(key=lambda x: (-x[0], x[1], x[2]))

for i in result[0][3]:
    print(i, end=" ")

그리고 해당 집합 별로 밀도, 개수, 가장 작은 번호를 가진 노드를 확인하고 조건에 맞게 정렬을 해준 후, 출력한다.
 

❍ CODE_UNION

import sys
from collections import defaultdict

input = sys.stdin.readline

def find_parent(a):
    if parent[a] != a:
        return find_parent(parent[a])
    else:
        return a

def union(a, b):
    a = find_parent(a)
    b = find_parent(b)

    if a < b:
        parent[a] = b
    else:
        parent[b] = a

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
parent = [i for i in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    union(a, b)

u = defaultdict(list)
for i in range(1, n + 1):
    p = find_parent(i)
    u[p] += [i]

result = []
for values in union.values():
    count = 0
    for j in values:
        count += len(graph[j])
    result.append((count / len(values), len(values), min(values), values))

result.sort(key=lambda x: (-x[0], x[1], x[2]))

for i in result[0][3]:
    print(i, end=" ")

---

해설 코드에 따라 bfs로도 문제를 풀이해보았다.
 

❍ bfs

def bfs(start):
    queue = deque([start])
    component = set()
    while queue:
        q = queue.popleft()
        visited[q] = True
        component.add(q)
        for i in graph[q]:
            if not visited[i]:
                queue.append(i)
    
    edge = 0

    for i in component:
        for j in graph[i]:
            if i in graph[j]:
                edge += 1
    
    return sorted(list(component)), edge / len(component)

시작 노드로부터 방문하지 않은 노드를 방문하면서 component에 담아준다.
그 후 간선의 개수를 세어주기 위해 component 속 노드끼리 연결된 간선을 찾아준다.
그 후, component를 오름차순, 밀도를 계산하여 return 한다.
 

❍ CODE_BFS

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

result = []
max_density = 0

for i in range(1, n + 1):
    if not visited[i]:
        component, density = bfs(i)
        '''
        실수값끼리 ==을 이용하여 비교하는 것보다 아래처럼 사용하여 비교하는 것이 안전하다.
        두 실수값의 차이가 1e-8보다 작다면, 같은 값이라고 생각한다.
        '''
        if abs(density - max_density) < 1e-8:
            if len(result) > len(component):
                result = component
                max_density = density
            elif len(result) == len(component):
                if result[0] > component[0]:
                    result = component
                    max_density = density
        
        elif density > max_density:
            result = component
            max_density = density

print(*result)

실수값끼리는 정수처럼 비교하면 오차가 발생할 수 있기 때문에, ==을 이용하여 비교해줄 수 없다. 따라서 위처럼 둘의 차이가 1e-8보다 작다면, 같은 값이라고 생각하도록 한다.

1. 가장 밀도가 높을 것
2. 컴포넌트의 개수가 적을 것
3. 더 작은 번호를 가진 컴퓨터가 있는 컴포넌트일 것

이 세 가지 조건을 차례대로 비교하여 최종적인 답을 출력할 수 있다.
 

---

❏ 삽질 기록

❍ Issue #1

[Tips] Python float형(부동소수점) 계산 오차 발생 이유 및 해결법

지금 문제의 경우 데이터 수가 많지 않아서 통과를 하는데, 실제로 다른 문제의 경우에는 풀리지 않을 수도 있다는 알고리즘 왕고수님의 조언에 따라서 부동 소수점에서 오차가 발생하는 경우와 해결법에 대해 새로 알 수 있게 되었다.

따라서 위의 문제의 경우도 위 블로그에서 나온 것처럼 해결법을 이용해주거나, 단순히 정렬만 해주는 문제이기에 a / b < c / d를 a * b < c * d로 바꾸어 정렬해주어도 해결된다.