2/12 Coding Test

✅ Coding Test

🎈 1922 네트워크 연결

컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하고자 하낟. 하지만 허브가 없어 직접 연결을 수행해야 하는데, 모두가 자료를 공유하기 위해선 모든 컴퓨ㅓ가 여결되어 있어야 한다.

이왕이며 컴퓨터를 연결하는 비용을 최소로 하여 연결하고자 할 때, 최소 비용을 구하는 문제.

입력값으 다음과 같다.

첫 줄은 컴퓨터 수, 둘째 줄에는 연결할 수 있는 선의 수, 셋째 줄부터 m줄만큼 각 컴퓨터를 연결하는데 드는 비용이 주어진다. (a, b, c 순서로 a컴퓨터에서 b컴퓨터로 이동하는데 c만큼 비용 발생)

# 1 Prim 알고리즘 풀이
import sys, heapq
input = sys.stdin.readline

n = int(input())
m = int(input())
visited = [False] * (n+1)
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((c, b))
    graph[b].append((c, a))
# 최초 비용 0, 시작 지점 1로 시작
queue = []
heapq.heappush(queue, (0, 1))
answer = 0
def prim():
    global answer
    while queue:
        cost, now_node = heapq.heappop(queue)
        if not visited[now_node]:
            visited[now_node] = True
            answer += cost
            for next_cost, next_node in graph[now_node]:
                heapq.heappush(queue, (next_cost, next_node))
    return answer

print(prim())

< 해설 >

프림 알고리즘을 활용한 풀이. (현재 노드 기준 최소 비용 확인을 위해 힙에 넣고 뺼 때 간선에 매겨진 가중치를 기준으로 넣기)

• 양방향 그래프 생성 후 (힙에 비용을 기준으로 삽입, 꺼내기 위해 비용을 먼저 그래프에 넣는다.)
• 이후 힙에 최초 비용, 시작노드를 담고 방문하지 않은 조건에 한해 다음 인접 노드 탐색 진행.

# 2 Kruskal 알고리즘
import sys
input = sys.stdin.readline

def find_parent(parent, a):
    if parent[a] != a:
        parent[a] = find_parent(parent, parent[a])
    return parent[a]

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 = int(input())
m = int(input())
parent = [i for i in range(n+1)]
graph = []
for _ in range(m):
    a, b, c = map(int, input().split())
    graph.append((c, a, b))

graph.sort(key=lambda x:x[0])
answer = 0
for cost, x, y in graph:
    if find_parent(parent, x) != find_parent(parent, y):
        union_parent(parent, x, y)
        answer += cost
print(answer)

< 해설 >

크루스칼 알고리즘을 활용한 풀이

• union-find 알고리즘을 활용해 함수 미리 만들어 주기.
• 이후 그래프에 비용을 기준으로 확인해주기 위해 비용, a, b 순서로 삽입
• 간선에 매겨진 가중치를 기준으로 오름차순 정렬
• 이후 for 루프를 기반으로 x와 y의 부모노드가 다르면 union 진행하고 비용 처리

💯 스패닝트리

모든 정점을 연결하는 가장 작은 최소비용을 구하는 문제는 결국, 모든 정점을 연결하는 최소 연결 횟수 (노드-1)개로 연결된 트리 형태이기에 스패닝트리를 구현하는 문제이다. (단, 사이클이 있어선 안된다.)

스패닝트리 풀이에는 프림, 크루스칼이 존재하는데 간략하게 정의를 한 번 다시 살펴보고자 한다.

프림

• 시작 노드 기준 연결된 edge 중 가중치가 가장 작은 edge와 연결된 노드를 추가하며 가장 최소 비용으로 탐색 진행해 간선 수가 n-1개면 중단.
• 시작 복잡도는 O(간선수 * log노드수)
  -> 다익스트라의 경우 한 정점에서 최소비용이 드는 순서대로 모두 방문한다면, 프림의 경우는 최소 비용 1개만을 골라 이동하는 방식

크루스칼

• 그리디 방식으로 네트워크 내 모든 정점을 최소 비용으로 연결해 최적 해답을 구하는 방법.
• 간선 선택을 기반으로 이동하며 이전 단계에서의 만들어진 트리와 별개로 무조건 현재 기준 최소 비용이 드는 간선을 선택하는 방식이다.
• 간선을 기준으로 추가하기 때문에 사이클 여부를 반드시 확인해야 하고 현재 노드를 기준으로 간선 당 비용들을 오름차순 정렬해 확인해야 한다.)