[SWEA 1251][Python][S/W 문제해결 응용] 4일차 - 하나로

코드1 : prim 풀이

## SWEA 1251
def prim(start):
    global result
    dist_arry[start] = 0
    for _ in range(N):
        local_min = float("inf")
        for i in range(N):
            if visited[i] == 0 and dist_arry[i] < local_min :
                min_node = i
                local_min = dist_arry[i]
        visited[min_node] = 1
        result += E*local_min

        for j in range(N):
            if visited[j] == 0 :
                tmp = (x_arry[min_node] - x_arry[j])**2 + (y_arry[min_node] - y_arry[j])**2
                dist_arry[j] = min(tmp, dist_arry[j])

T = int(input())
for test_case in range(1, T+1):
    N = int(input())
    x_arry = list(map(int,input().split()))
    y_arry = list(map(int,input().split()))
    E = float(input())

    visited = [0]*N
    dist_arry = [float("inf")]*N
    result = 0
    prim(0)

    print(f"#{test_case} {round(result)}")

풀이1

최소신장트리(MST : Minimun Spanning Tree) 문제로 Prim 알고리즘을 이용해 풀었다. ( 아래에서 kruskal도 해봄 )

현재 노드에서 방문하지 않은 노드와의 거리를 구하여, dist_arry를 업데이트하고, 

업데이트된 dist_arry를 바탕으로 가장 작은 거리를 가지는 node를 다음번에 방문할 node로 선정한다. 

모든 노드를 방문할때까지 위 과정을 반복한다.  

 

 

 

코드2 : kruskal 풀이

## SWEA 1251 : kruskal
def find(x):
    if root[x] != x :
        root[x] = find(root[x])
    return root[x]
def union(x,y):
    x = find(x)
    y = find(y)
    if x < y :
        root[y] = x
    else :
        root[x] = y
def kruskal():
    global result
    ## 노드간 거리를 미리 구해서 list에 넣음( heapq 대용 )
    for i in range(N):
        for j in range(i, N):
            tmp = E * ((x_arry[i] - x_arry[j]) ** 2 + (y_arry[i] - y_arry[j]) ** 2)
            dist_arry.append((tmp, i, j))
    dist_arry.sort() ## 오름차순 정렬
    for dist, i, j in dist_arry:
        if find(i) != find(j):
            union(i, j) ## 유니온을 통해 루트 수정
            result += dist ## 거리가 가장 가까운 노드를 결과값에 더해줌

T = int(input())
for test_case in range(1, T+1):
    N = int(input())
    x_arry = list(map(int,input().split()))
    y_arry = list(map(int,input().split()))
    E = float(input())
    dist_arry = []
    result = 0
    root = list(range(N))
    kruskal()
    print(f"#{test_case} {round(result)}")

풀이2

kruskal알고리즘에서는 노드별 root list를 생성하여  find, union 함수로  각 노드의 root node를 찾아내야한다. 

그러기 위해서 노드간 거리를 모두 구한 후, 오름차순으로  정렬하여 거리가 가장 짧은 노드부터 방문해야한다.