[구름톤 챌린지 #17] 통신망 분석

문제17. 통신망 분석

구름LEVEL

---

---

문제 해결 방법

오늘 문제는 그래프 표현 방법들을 알고 있고, 어떤 표현 방식이 적절한지를 판단할 수 있어야 풀 수 있는 문제였다.

 

오늘 문제의 컴퓨터의 개수, 즉 노드의 개수는 최대 100,000 개이다. 이를 인접행렬을 이용해서 풀기 위해서는 N * N의 이차원 배열이 필요하므로 사용하게 되는 공간은 최대 100,000 * 100,000 = 10,000,000,000 이다. 실제로 인접 행렬 방식으로 문제를 풀어 제출하면, 많은 수의 테스트 케이스에서 Runtime Error가 나는데, 이는 메모리 초과로 인해 발생한 에러이다.

 

시간적인 문제도 있다. 문제 조건을 보면 간선의 최대 개수는 200,000 이다. 노드와 간선을 비교해보면 노드에 비해 간선의 수가 월등히 적은 희소 그래프인 것이다. 그런데 인접 행렬 방식을 사용하면 각 노드는 간선이 있을지 없을지도 모르는 10 만개의 다른 노드와 비교를 하게 된다. 예를 들어 1 개의 간선만 존재한다면, 1 개의 간선을 확인하기 위해 100 억 번의 비교를 수행하게 된다. 이는 엄청난 낭비이다. 실제로 인접 행렬 방식으로 문제를 풀어 제출했을 때, 시간초과가 발생하는 테스트 케이스도 있었다.

 

이러한 문제를 극복하기 위해서는 인접 리스트 방식을 사용하면 된다. 길이가 N인 1 차원 리스트를 만들고, 리스트의 각 요소를 빈 리스트로 초기화하는 것이다. 그 다음, 간선을 입력받으면서 간선이 있을 경우에만 해당 인덱스에 만들어둔 리스트에 연결된 노드를 추가하면 된다.

 

이렇게 그래프 표현 방식을 결정했다면, 나머지는 이전 문제들과 비슷한 방식으로 풀 수 있다. BFS를 이용해 컴포넌트로 묶이는 노드들을 골라내고, 그 컴포넌트 내부의 간선의 수를 구하면 된다. 참고로 간선의 수는 컴포넌트에 포함된 각 노드의 연결된 간선을 모두 더한 값을 2로 나누어 얻을 수 있다(양방향이니 중복되어 2번씩 세어진다). 마지막으로 그중 최대 밀집도를 갖는 컴포넌트를 찾아서 출력하면 된다.

 

위 내용을 코드로 구현하면 아래와 같다.

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())

graph = [[] for i in range(n+1)]


for i in range(m):
    node1, node2 = map(int, sys.stdin.readline().split())
    graph[node1].append(node2)
    graph[node2].append(node1)

visited = set()
max_density = 0.
max_density_component = []

for i in range(1, n +1):
    #이미 방문했으면 볼 필요 없음.
    if i in visited:
        continue

    dq = deque()
    dq.append(i)

    component = [i]
    visited.add(i)

    while dq:
        node1 = dq.popleft()
        for node2 in graph[node1]:

            if node2 in visited:
                continue

            component.append(node2)
            visited.add(node2)
            dq.append(node2)
	
    #밀도를 구하는 과정
    #길이가 1인 컴포넌트는 의미 없다.
    if len(component) == 1:
        continue

    edge_count = 0
    #길이가 1보다 큰 컴포넌트는 밀도를 구해야함
    for node1 in component:
        #중복되어 두번씩 체크되긴 하지만 어차피 밀도를 구하는 것이니 상관 없다.
        edge_count += len(graph[node1])

    density = edge_count / len(component)

    if max_density < density:
        max_density = density
        max_density_component = component
    elif max_density == density and len(max_density_component) > len(component):
        max_density_component = component

max_density_component.sort()

for node in max_density_component:
    print(node, end = " ")