[BOJ][🟡4][백준#01197] 최소 스패닝 트리

문제 출처

BAEKJOON Online Judge #1197

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다. 그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

예제

입력

3 3
1 2 1
2 3 2
1 3 3

출력

3```

<br>

## My Sol

```python
import sys
input = sys.stdin.readline
from heapq import heappop, heappush


def find_set(x):
    global p
    if x != p[x]:
        p[x] = find_set(p[x])
    return p[x]


def union(u, v, w):
    global cnt, ret, p
    a, b = find_set(u), find_set(v)
    if a != b:
        p[a] = b
        ret += w
        cnt += 1


V, E = map(int, input().split())
Q = []
for _ in range(E):
    u, v, w = map(int, input().split())
    heappush(Q, (w, u, v))

p = [i for i in range(V+1)]
ret = 0
cnt = 0
while cnt < V-1:
    w, u, v = heappop(Q)
    union(u, v, w)

print(ret)

graph 이론의 유니온 파인드와 크루스칼 알고리즘을 활용해 문제를 풀었다.

1. 입력을 처리하여 한 곳에 간선 정보를 모두 모은다.
2. 가중치가 짧은 순서대로 정렬한다. 나는 우선순위 큐(heap)를 사용하였다.
3. 하나하나 뽑아서 두 노드의 루트노드가 같은지 확인한다.
4. 같다면 이미 가중치가 더 작은 간선으로 연결된 것이므로 넘어간다.
5. 같지 않다면 해당 가중치가 두 노드를 연결하는 가장 작은 가중치의 간선이다.
6. 유니온 함수를 이용해 가중치를 결과값에 더하고 카운트를 1 증가, 두 노드의 루트 노드를 같게 이식해준다.
7. 카운트가 V-1, 즉 모든 노드가 연결되면 반복을 종료한다.
8. 결과값을 출력한다.

항상 union 함수에서 p[a] = b 부분이 너무 헷갈렸다. 이 부분을 잘 숙지하도록 하자.

결과

맞았습니다!!

모범답안

출처

from sys import stdin

read = stdin.readline
V, S = map(int, read().split())

edge = []
for _ in range(S):
    a, b, w = map(int, read().split())
    edge.append((w, a, b))

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

parent = list(range(V + 1))


def union(a, b):
    a = find(a)
    b = find(b)

    if b < a:
        parent[a] = b
    else:
        parent[b] = a


def find(a):
    if a == parent[a]:
        return a
    parent[a] = find(parent[a])  # 경로 압축
    return parent[a]


sum = 0
for w, s, e in edge:
    if find(s) != find(e):
        union(s, e)
        sum += w

print(sum)

연산속도가 20% 정도 빠른 풀이를 발견해서 분석해보려 한다. 그런데 내 코드랑 특별히 다른 부분은 없고, 나는 heap을 이용했지만 이 분은 list로 입력을 처리한 뒤, 한 번에 sort를 이용해 가중치별로 정렬하셨다.

그런데 조금 다르다고 느낀 점은 union에서 a와 b의 크기를 비교하여 더 작은 루트 노드 번호로 갱신되도록 했다는 점이 특이했다. 어차피 같은지 여부를 판단하기 때문에 크게 의미가 없지 않은가?

heap이 더 빠르다고 생각했는데 list와 정렬 방식이 더 빠르기 때문이라는 점이 연산속도의 결정적 요인이라고 느꼈고, 이 때문에 내 풀이에서 list와 정렬을 사용해 다시 문제를 풀어보았다.

import sys
input = sys.stdin.readline


def find_set(x):
    global p
    if x != p[x]:
        p[x] = find_set(p[x])
    return p[x]


def union(u, v, w):
    global cnt, ret, p
    a, b = find_set(u), find_set(v)
    if a != b:
        p[a] = b
        ret += w
        cnt += 1


V, E = map(int, input().split())
Q = []
for _ in range(E):
    u, v, w = map(int, input().split())
    Q.append((w, u, v))
Q.sort()

p = [i for i in range(V+1)]
ret = 0
cnt = 0
i = 0
while cnt < V-1:
    w, u, v = Q[i]
    union(u, v, w)
    i += 1

print(ret)

연산속도가 480ms에서 380ms로 20% 정도 감소하였다. 역시 heap이 문제였다.