[Python][백준 1922번] 네트워크 연결 ( 프림, 크루스칼 )

# 크루스칼  ----
def find_parent(arr, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]


def union(arr, a, b):
    # 맨처음에는 자기 자신의 값으로 parent가 설정되어 있다 ex) 1, 4
    # 이 경우에는, 그냥 큰 애에다가, 작은 애를 합친다
    a = find_parent(arr, a)
    b = find_parent(arr, b)
    if a > b:
        parent[b] = a
    else:
        parent[a] = b


n = int(input())
m = int(input())
edges = []
parent = [-1] * (n+1)
res = 0

# 부모 정보 초기화
for i in range(len(parent)):
    parent[i] = i

for _ in range(m):
    st, ed, cost = map(int, input().split())
    edges.append((cost, st, ed))
# edges 정렬
edges.sort()
for edge in edges:
    cost, st, ed = edge

    if find_parent(parent, st) != find_parent(parent, ed):
        res += cost
        union(parent, st, ed)
print(res)

# prim 알고리즘
sys.stdin = open("input.txt", "rt")
sys.setrecursionlimit(100000)


def prim(W):  # W : 입력받은 연결 정보
    # 초기화 작업
    # len(W) 이란, 노드의 개수를 말하는 것이다. 그런데, 우리는 W에 임의의 노드 개수 1을 추가했다
    # n 은 사실상, 실제 노드의 개수를 말하게 될 것이다.
    n = len(W) - 1
    F = []
    nearest = [-1] * (n + 1)
    distance = [-1] * (n + 1)

    # 1 노드를 시작점으로 setting 하여 초기화
    for i in range(2, n + 1):
        nearest[i] = 1
        distance[i] = W[1][i]

    for _ in range(n-1):  # n - 1개의 edge가 선택될 때까지 반복
        minVal = 10001
        for i in range(2, n + 1):
            '''
            Y에 선택되지 않은 노드 중에서
            Y집단에 가장 가까운 거리에 있는 노드를 선택하는 과정 
            '''
            if(0 <= distance[i] and distance[i] < minVal):
                minVal = distance[i]
                vnear = i  # vnear에는 Y에 속하지 않은 노드 중, Y에 가장 가까운 노드가 들어간다

        edge = (nearest[vnear], vnear, W[nearest[vnear]][vnear])
        F.append(edge)  # 프림 알고리즘 진행 과정에서 선택한 edge 정보가 들어간다
        distance[vnear] = -1

        # 자. 이제 다시 distance[i] 값들을 update 시켜주어야 한다
        # Y에 vnear라는 새로운 노드가 추가되었기 때문에
        # vnear라는 노드와의 거리를 기준으로 다시 distance[i]를 update 시켜주어야 한다는 것이다
        for i in range(2, n+1):
            if(distance[i] > W[i][vnear]):
                distance[i] = W[i][vnear]
                nearest[i] = vnear  # 가장 가까운 node 정보고 update
    return F
#


# 최대비용 : 10001
nodes = int(sys.stdin.readline())
paths = int(sys.stdin.readline())
W = [[10001] * (nodes + 1) for _ in range(nodes + 1)]
res = 0

# 0번째 col, 0번째 row는 -1로 초기화해준다
for i in range(nodes + 1):
    W[0][i] = -1

for i in range(nodes + 1):
    W[i][0] = -1

# 자기 자신까지의 거리는 0으로 만들어준다
for i in range(1, nodes + 1):
    W[i][i] = 0

# 연결정보를 저장한다.
for _ in range(paths):
    st, ed, cost = map(int, sys.stdin.readline().strip().split())
    W[st][ed] = cost
    W[ed][st] = cost

F = prim(W)

for f in F:
    res += f[2]

print(res)