[BOJ/Python] 2406_안정적인 네트워크

문제 출처:https://www.acmicpc.net/problem/2406

2406번: 안정적인 네트워크

문제

한 회사는 본사와 지사의 컴퓨터들을 연결하는 네트워크 시설을 보유하고 있다. 각 지사에는 네트워크용 컴퓨터가 한 대씩 있으며, 이들은 본사의 메인 컴퓨터와 직접 연결되어 있다. 몇몇 지사들끼리 연결되어 있는 경우도 있다.

네트워크 시설에서는 두 컴퓨터가 직접 연결되어 있지 않더라도 다른 컴퓨터들을 경유하여 연결될 수 있다. 예를 들어 1, 2번 컴퓨터가 직접 연결되어 있고, 1, 3번 컴퓨터가 직접 연결되어 있다면, 이것은 2, 3번 컴퓨터가 연결되어 있는 효과도 발휘한다는 것이다.

회사 측에서는 네트워크에 고장이 발생하더라도 컴퓨터들이 연결되어 있도록 안정적인 네트워크를 구축하고자 한다. 네트워크에 고장이 발생하는 경우는 두 가지가 있다. 첫 번째는 직접 연결되어 있는 두 컴퓨터의 연결이 끊어지는 경우이다. 회사 측은 이런 경우에도 이 두 컴퓨터가 다른 컴퓨터들을 경유하여 연결되어 있기를 원한다. 두 번째는 컴퓨터가 고장 나는 경우이다. 회사 측은 이런 경우에는 고장 나지 않은 컴퓨터들끼리 연결되어 있기를 원한다.

예제로 주어진 입력에서 1, 2번 컴퓨터의 연결이 끊어지더라도, 이 두 컴퓨터는 3번 컴퓨터를 통해서 연결되게 된다. 하지만 1번 컴퓨터가 고장 나는 경우에는 5번 컴퓨터가 다른 컴퓨터들과 연결되어 있지 못하게 된다. 따라서 5번 컴퓨터를 다른 컴퓨터와 직접 연결해 주어야 한다.

두 컴퓨터를 연결하는 데 소요되는 비용은 일정하지 않다. 당신은 네트워크의 연결 상태를 입력받아 이 네트워크가 안정적인 네트워크인지 판별하고, 만약 아닐 경우에는 최소 비용으로 회사의 네트워크가 안정적이 되도록 하여야 한다.

입력

첫째 줄에 두 정수 n(1 ≤ n ≤ 1,000), m(0 ≤ m ≤ 10,000)이 주어진다. n은 컴퓨터의 개수이며, m은 연결되어 있는 지사 컴퓨터들의 쌍의 개수이다. 다음 m개의 줄에는 두 정수 x, y가 주어진다. 이는 서로 다른 두 컴퓨터, x번 컴퓨터와 y번 컴퓨터가 직접 연결되어 있음을 의미한다. 다음 n개의 줄에는 인접 행렬의 형태로 두 컴퓨터를 연결할 때 드는 비용이 주어진다. 이 값은 1 이상 30,000이하의 정수이며, i번 컴퓨터와 j번 컴퓨터를 연결할 때 드는 비용은 j번 컴퓨터와 i번 컴퓨터를 연결할 때 드는 비용과 같다. 본사의 컴퓨터는 항상 1번 컴퓨터이다.

출력

첫째 줄에 최소 비용 X와 연결할 컴퓨터들의 쌍의 개수 K를 출력한다. 다음 K개의 줄에는 두 정수로 연결할 컴퓨터들의 번호를 출력한다. 만약 주어진 입력이 안정적인 네트워크라면 X=0이고 K=0이 된다.

예제 입력 1

5 2
3 2
3 4
0 100 50 100 100
100 0 100 100 100
50 100 0 20 100
100 100 20 0 80
100 100 100 80 0

예제 출력 1

80 1
5 4

---

풀이

 

문제를 요약해 보면 다음과 같다.

 

1. 본사의 컴퓨터는 1번 컴퓨터이고, 각 지사의 컴퓨터는 이 컴퓨터와 직접 연결되어 있다.
2. 두 컴퓨터가 직접 연결되어 있지 않더라도 다른 컴퓨터들을 경유하여 연결될 수 있다.
3. 만약 1번 컴퓨터가 고장 났을 경우, 다른 컴퓨터와 연결되지 않은 컴퓨터의 네트워크는 불안정하므로 이를 해결하기 위하여 연결해야 하는 컴퓨터의 쌍과, 그 최소 비용을 구하는 문제이다.

현재 연결되어 있는 상태를 바탕으로 2번 컴퓨터 ~ N번 컴퓨터의 MST를 구하는 문제이다. 하지만, 초기 연결 상태에서 사이클이 존재할 수도 있으므로 간선의 개수가 N-2개임을 보장할 순 없다.

 

코드는 다음과 같다.

 

import sys
 
def find_parent(parent,x):
    if parent[x] != x:
        parent[x] = find_parent(parent,parent[x])
    return parent[x]
 
def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
 
    if a<b:
        parent[b] = a
    else:
        parent[a] = b
 
 
n,m = map(int,sys.stdin.readline().split())
parent = [i for i in range(n+1)]
for _ in range(m):
    x,y = map(int,sys.stdin.readline().split())
    union_parent(parent,x,y)
 
cost = []
for _ in range(n):
    cost.append(list(map(int,sys.stdin.readline().split())))
 
edges = []
 
for i in range(1,n):
    for j in range(i+1,n):
        edges.append((cost[i][j],i+1,j+1))
 
edges.sort()
 
total_cost = 0
k = 0
k_list = []
for cost,x,y in edges:
    if find_parent(parent,x)!=find_parent(parent,y):
        union_parent(parent,x,y)
        total_cost+=cost
        k_list.append((x,y))
        k+=1
 
print(total_cost,k)
if k>0:
    for x,y in k_list:
        print(x,y)

• 2차원 행렬의 정보를 바탕으로 간선(두 컴퓨터들의 연결) 정보를 만들고, edges에 저장한다.
• 여기서 2번 컴퓨터 ~ N번 컴퓨터까지의 MST를 구해야 하므로, 간선 정보 또한 2번 컴퓨터 ~ N번 컴퓨터에 대하여 생성한다.
• 간선들을 오름차순으로 정렬하고, 사이클이 생성되지 않도록 하여 연결한다.
• 최종적으로 비용과 연결된 간선의 개수를 출력한다.
• 추가적으로 연결된 간선이 1개 이상이라면, 두 컴퓨터의 정보를 출력한다.