[백준] 17398번: 통신망 분할

🔈 문제

BOJ의 인기스타, 방송인 권욱제는 통신 회사에 취업했다. 현재 이 통신 회사는 너무나 큰 통신망을 한 지사에서 관리하느라 큰 비용을 지불하고 있었다. 그래서 회사는 최근 IT의 트렌드 중 하나인 '탈중앙화'에 편승하여, 통신망을 분할하도록 결정했다. 그래서 욱제한테 통신망을 분할 할때 발생하는 비용을 분석하도록 지시했다.
현재 회사 망에는 1번부터 N번까지 총 N개의 통신 탑이 존재하며, 통신탑 간의 연결이 M개 존재한다. 이때 회사에서는 총 Q번 통신탑 간의 연결을 제거함으로써 하나의 통신망을 여러 개의 통신망으로 분리하려고 한다. 통신망이란, 통신탑의 연결을 통해 도달 가능한 통신탑들의 집합이다. 통신탑 간의 연결 관계를 제거할 때 드는 비용은 제거한 후 통신망이 두 개로 나누어진다면 나눠진 두 개의 통신망에 속한 통신탑들의 갯수의 곱이 되며, 나누어지지 않을 경우 0이다.

 

<그림 1>

그림 1을 예시로 할때, 연결 (3, 4)를 제거하면 {1, 2, 3}, {4, 5, 6}으로 분할 되며, 이때 발생하는 비용은 3 × 3 = 9가 된다. 대신 연결 (2, 3)을 제거하면, 망이 나눠지지 않았기에 비용은 0이 된다.
욱제는 회사의 요청에 따라 Q번의 제거를 통해 나오는 비용의 합을 구해야 한다. 하지만 욱제는 회사의 통신망을 이용해 방송하기 바쁘기 때문에 우리가 도와주자.

 

📝입력

첫 번째 줄에는 통신탑의 개수인 자연수 N, 통신탑 사이의 연결의 개수인 자연수 M, 통신망 연결 분할 횟수인 자연수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000, 1 ≤ Q ≤ M)
두 번째 줄부터 M개의 줄에 걸쳐 두 개의 자연수 X, Y가 공백으로 구분되어 주어진다. 이는 X 통신탑과 Y 통신탑 사이에 연결이 있음을 뜻한다. (1 ≤ X, Y ≤ N, X ≠ Y)

중복된 연결은 주어지지 않으며, 모든 통신탑은 처음엔 하나의 통신망에 속한다. 조건에 의해 자기 자신과 연결이 있는 통신탑은 없다.

그 다음 줄부터 Q개의 줄에 걸쳐 제거될 연결의 번호인 자연수 A가 주어진다. 이는 A번째로 입력된 (X, Y)의 연결이 제거되었음을 의미한다. (1 ≤ A ≤ M)
이미 제거된 연결은 다시 제거되지 않으며, 제거는 입력 순서대로 진행된다.

 

📑출력

첫 번째 줄에 Q개의 연결을 순서대로 제거하는데 드는 비용의 합을 출력한다.

 

📚 문제 풀이

 

문제가 재밌어서 오랜만에 풀이글을 작성한다.

 

유니온 파인드를 사용해서 쉽게 간선을 연결하는 방법은 배웠지만, 반대로 간선을 제거하는 방법은 생각해본적이 없었다. 

이 문제를 해결하기 위해 고민해보았는데, 각 간선제거마다 제거된 간선 말고 다른 경로를 통해서 이동이 가능한지 탐색을 해야하기 때문에 시간 복잡도 $O(V+E)$ 을 $Q$ 번 수행하므로 시간초과가 발생한다.

 

하지만 간선을 제거하는 것이 아니라 연결하는 것으로도 이 문제는 해결 가능하다. 

 

Q개의 연결된 간선을 지우는데, 다시 말하면 M - Q 의 간선은 지워지지 않는다. 입력된 Q개의 간선을 제외하고 M - Q개의 간선을 이어준다.

 

현재 상태는 Q개의 간선을 모두 지우고 난 뒤의 그래프이다. 

 

지워야 하는 Q개의 간선 중 제일 마지막 간선 $X$ 에 의해 연결되어 있는 A와 B의 부모가 같다면 간선 $X$를 지워도 이 둘은 연결되어 있다는 뜻이다. 반대로 부모가 다르다면 $X$가 제거됨으로써 둘이 나눠졌다는 것을 의미한다.  

 

이 점을 이용하여 Q개의 간선을 연결하는 작업을 거꾸로 진행한다. 

 

각각의 노드마다 연결되어 있는 노드의 갯수도 따로 저장한다.

 

💻 코드

from sys import stdin
input = stdin.readline
 
def find(x:int, parent:list[int]) -> int:
    if x != parent[x]:
        parent[x] = find(parent[x], parent)
    return parent[x]
 
def union(a:int, b:int, parent:list[int]) -> None:
    a = find(a, parent)
    b = find(b, parent)
 
    if a < b:
        parent[b] = a
        cost[a] += cost[b]
    elif a > b:
        parent[a] = b
        cost[b] += cost[a]
 
n,m,q = map(int,input().split())
graph = [[] for _ in range(n+1)]
tree = []
edges = [tuple(map(int,input().split())) for _ in range(m)]
 
tmp = [False]*m
cut = []
 
parent = [i for i in range(n+1)]
cost = [1 for _ in range(n+1)]
 
for _ in range(q):
    k = int(input())-1
    cut.append(k)
    tmp[k] = True
 
for i in range(m):
    if not tmp[i]:
        x,y = edges[i]
        if find(x, parent) != find(y, parent):
            union(x,y,parent)
 
ans = 0
 
for i in range(q-1, -1, -1):
    x,y = edges[cut[i]]
    if find(x, parent) != find(y, parent): # 둘의 부모가 다르다면 이건 이어졌던것
        ans += cost[find(x, parent)] * cost[find(y, parent)]
        union(x,y,parent)
 
print(ans)

 

🍭 시행착오

 

첫번째 틀렸던 이유는 각각 노드마다 연결되어 있는 노드의 수를 확인할 때 실수가 있었다. 

 

🔗 문제링크 통신망 분할

17398번: 통신망 분할