백준 2406 : 안정적인 네트워크 (Python)

본문 링크

import sys
input=sys.stdin.readline

"""
본사의 컴퓨터는 항상 1번 컴퓨터이다.
한 회사는 본사와 지사의 컴퓨터들을 연결하는 네트워크 시설을 보유하고 있다. 
각 지사에는 네트워크용 컴퓨터가 한 대씩 있으며, 이들은 본사의 메인 컴퓨터와 직접 연결되어 있다. 
"""
def Find(x):
    if x!=disjoint[x]:
        disjoint[x]=Find(disjoint[x])
    return disjoint[x]

def Union(a,b):

    a=Find(a)
    b=Find(b)

    if a>b:
        disjoint[a]=b
    else:
        disjoint[b]=a

N,M=map(int,input().split())

disjoint=[ _ for _ in range(N+1) ] ; total=0 ; node=[]
for i in range(M):
    u,v=map(int,input().split())
    Union(u,v)

check=set()
for i in range(2,N+1):

    if Find(i) not in check:
        check.add(Find(i))

if len(check)==1:
    print("0 0")
    exit(0)

graph=[ list(map(int,input().split())) for _ in range(N) ]

edge=[]

for i in range(N):
    for j in range(N):
        if i==0 or j==0:
            continue

        edge.append((graph[i][j] , i+1 , j+1 ))

edge.sort(key=lambda x:x[0])

for value,A,B in edge:

    x=Find(A)
    y=Find(B)
    if x!=y:
        if x>y:
            disjoint[x]=y
        else:
            disjoint[y]=x
        node.append([A,B])
        total += value

print(total,len(node))
for i in range(len(node)):
    print(*node[i])

📌 어떻게 접근할 것인가?

문제를 잘 읽어야한다. 본사의 컴퓨터는 항상 $1$ 번이고 , 본사는 다른 컴퓨터 전체와 연결되어있다.

따라서 본사컴퓨터인 $1$ 번 노드를 제외하고 최소 스패닝 트리를 구성하면 된다.

따라서 edge 에 노드와 가중치를 입력받을때 i==0 or j==0 인 경우는 입력을 받지않는다.

나머지 부분은 크루스칼 알고리즘을 구현해주면 된다.