백준pyton_네트워크연결(Prim,Kruskal)

https://www.acmicpc.net/problem/1922

전형적인, 최소신장 트리 문제이다
모든 정점을 연결할 수 있는 최소 가중치 edge들의 합을 구하는 것

1. kruskal 알고리즘

import sys
sys.stdin = open("input.txt", "rt")
from collections import deque, Counter
sys.setrecursionlimit(100000)

'''
크루스칼 알고리즘의 경우,
서로소 집합을 사용한다.
( union-find 자료구조)

사이클을 방지해야 하는 것이 초점이기 때문에
union-find 과정을 통해,
해당 edge를 선택했을 때, 사이클이 발생하는지 안하는지를 주의깊게 봐야 한다.
사이클여부를 판단하기 위해,
연결된 노드들을 하나의 집합으로 만들어야 한다
그리고, 하나의 집합으로 만드는 방법은, 같은 집합에 속한 노드들이
같은 루트 노드를 지니게 하는 것이다. 

이를 위해 union-find를 사용하는데
각 노드들의, 부모 정보가 담긴 배열 p를 선언해두고

해당 edge를 선택할 때마다
배열p를 보면서,

해당 edge를 선택할 시,
연결된 2개의 노드가, 같은 루트노트를 지니는가
즉, 같은 집합에 속하는가 를 검사한 이후,
같은 집합에 속하면, 해당 edge를 버리고
같은 집합에 속하지 않으면 edge를 선택한 이후,
동일한 집합으로 만들어준다 ( union ) 


'''
import sys
sys.setrecursionlimit(100000)

class DisjointSet:
    def __init__( self, n ) : # n : n개의 노드
        self.U = [ ] # 부모 집합
        for i in range(n):
            # 자기 자신을 부모로 갖게 한다.
            self.U.append(i)

    # 부모를 찾는 함수
    def find( self, i ):
        j = i
        while( self.U[j] != j ) :
            # 자기 자신의 부모가, 자기 자신을 가리킬 때까지
            # 밑에서부터 위로 올라가는 구조이다
            j = self.U[j]
        return j

    # union 시, 더 작은값으로, 더 큰 값의 부모로 설정해준다.
    def union(self, p, q) :
        if( p < q ):
            self.U[q] = p
        else:
            self.U[p] = q

    # find함수를 통해, p, q 에 대한 루트 노드를 반환 받으면
    # 비교하여 setting 한다
    def equal( self, p, q ) :
        if( p == q ):
            return True
        else:
            return False

# 크루스칼 알고리즘
def kruskal( n , E ) : # E : 가중치 순서대로 sort된 상태여야 한다
    F = [ ] # 선택된 edge 정보들을 저장할 배열
    dset = DisjointSet(n) # n만큼 disjoint set을 만든다. n은 정점 집합의 크기
    while( len(F) < n - 1) : # F의 size가 n-1이 될때까지 ( edge의 개수 )
        edge = E.pop(0) # 앞의 것을 뽑는다
        # 이러한 logic이 가능한 이유는 E를, 가중치 기준으로 오름차순 sorting 했기 때문이다.
        i, j  = edge[0], edge[1]
        p = dset.find( i - 1 ) # 루트 노드를 찾는다  > i - 1을 해주는 이유는, 배열상 idx 접근을 위해
        q = dset.find( j - 1 )

        # 사이클을 형성하지 않는다면, 같은 루트 노드를 지니지  않는다면
        if( not dset.equal(p,q) ) : # 집합이 서로 다르다면
            dset.union( p, q )
            F.append(edge)
    return F


node = int(sys.stdin.readline())
path = int(sys.stdin.readline())
E = []
res = 0

for _ in range(path):
    st, ed , cost = map(int, sys.stdin.readline().strip().split())
    E.append([st,ed,cost])

# E를 가중치 순으로 sort > kruskal을 위한 필수 과정
E.sort( key = lambda x : x[2] )

F = kruskal(node,E)

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

print(res)

            
        

2. prim 알고리즘

import sys
sys.setrecursionlimit(100000)

'''
Prim 알고리즘은, kruskal 알고리즘과 성격이 다소 다르다.

kruskal 알고리즘은, 애초부터 간선들을 가중치 순으로 sort한 이후,
가중치가 낮은 간선부터 조사해가면서
해당 간선이 사이클을 만들면 버리고
사이클을 만들지 않으면, 추가한 이후, union 하는 과정을 거쳤다

하지마, Prim 알고리즘의 경우는 다소 다르다.
Prim 알고리즘의 경우,

V를 전체 노드 집합이라고 한다면  
임의의 한 노드를 선택하고

'''

def prim(W) : # W : 입력받은 연결 정보
    # 초기화 작업
    # len(W)은 노드의 개수를 말하는 것이다. 그런데 W에 0번째 idx에 해당하는 col, row 추가한 상태
    # 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 # Y에 속하지 않은 노드 중에서 Y 집단에 가장 가까운 노드

        # nearest[vnear] : 출발점 노드
        # vnear : 새로 선택한 노드
        # W[nearest[vnear]][vnear]
        edge = ( nearest[vnear] , vnear, W[nearest[vnear]][vnear] )
        F.append(edge) # 프림 알고리즘 진행 과정에서 선택한 edge 정보가 들어간다
        distance[vnear] = -1 # 해당 distance를 방문 처리한 것으로 하기 위해 -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)