[코딩테스트] 그래프 이론

JY·2022년 7월 15일

코딩테스트

그래프 이론

Review

크루스칼 알고리즘: 그리디 알고리즘으로 분류
위상 정렬 알고리즘: 큐 자료구조 또는 스택 자료구조 활용해야 구현 가능

'서로 다른 개체가 연결되어 있다'라는 이야기를 들으면 가장 먼저 그래프 알고리즘을 떠올리자.

서로소 집합

서로소 집합(Disjoint Sets): 공통 원소가 없는 두 집합

서로소 집합 자료구조

: 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조

union 연산: 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
find 연산: 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

서로소 집합 자료구조 (=union-find 자료구조)
=> 두 집합이 서로소 관계인지를 확인할 수 있다는 말은 각 집합이 어떤 원소를 공통으로 가지고 있는지를 확인할 수 있다는 말

서로소 집합 자료구조 구현

트리 자료구조를 이용해서 집합을 표현하는 서로소 집합 계산 알고리즘

union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
1) A와 B의 루트 노드 A', B'을 각각 찾는다.
2) A'를 B'의 부모 노드로 설정한다. (B'가 A'를 가리키도록 한다.)
모든 union 연산을 처리할 때까지 1번 과정을 반복한다.

def find_parent(parent, x): # 특정 원소가 속한 집합 찾기
    if parent[x] != x:  # 루트 노드 아니라면
        return find_parent(parent, parent[x]) # 루트 노드 찾을 때까지 재귀 호출
    return x

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

v, e = map(int, input().split())  # 노드 수, 간선 수 입력 받기
parent = [0] * (v+1)

for i in range(1, v+1):  # 부모 테이블상에서 부모를 자기 자신으로 초기화
    parent[i] = i

for i in range(e):  # union연산 각각 수행
    a, b = map(int, input().split())
    union_parent(parent, a, b)

print('각 원소가 속한 집합: ', end='')  # 각 원소가 속한 집합 출력
for i in range(1, v+1):
    print(find_parent(parent, i), end=' ')

print()

print('부모 테이블: ', end='')  # 부모 테이블 내용 출력
for i in range(1, v+1):
    print(parent[i], end=' ')

find 함수를 다음과 같이 변경하면 경로 압축 기법의 구현 가능

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

개선된 서로소 집합 알고리즘 코드

def find_parent(parent, x):  # 특정 원소가 속한 집합 찾기
    if parent[x] != x:  # 루트 노드 아니라면
        parent[x] = find_parent(parent, parent[x])  # 루트 노드 찾을 때까지 재귀 호출
    return parent[x]

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

v, e = map(int, input().split())  # 노드 수, 간선 수 입력 받기
parent = [0] * (v+1)

for i in range(1, v+1):  # 부모 테이블상에서 부모를 자기 자신으로 초기화
    parent[i] = i

for i in range(e):  # union연산 각각 수행
    a, b = map(int, input().split())
    union_parent(parent, a, b)

print('각 원소가 속한 집합: ', end='')  # 각 원소가 속한 집합 출력
for i in range(1, v+1):
    print(find_parent(parent, i), end=' ')

print()

print('부모 테이블: ', end='')  # 부모 테이블 내용 출력
for i in range(1, v+1):
    print(parent[i], end=' ')

서로소 집합 알고리즘의 시간 복잡도

노드 개수가 V개이고, 최대 V-1개의 union 연산과 M개의 find 연산이 가능할 때 경로 압축 방법을 적용한 시간 복잡도
$O(V+M(1+log_{2-M/V}V))$

서로소 집합을 활용한 사이클 판별

서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용 가능
간선을 하나씩 확인하면서 두 노드가 포합되어 있는 집합을 합치는 과정을 반복하여 사용

각 간선을 확인하며 두 노드의 루트 노드를 확인한다.
1) 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행한다.
2) 루트 노드가 서로 같다면 사이클이 발생한 것이다.
그래프에 포함되어있는 모든 간선에 대하여 1번 과정을 반복한다.

def find_parent(parent, x):  # 특정 원소가 속한 집합 찾기
    if parent[x] != x:  # 루트 노드 아니라면
        parent[x] = find_parent(parent, parent[x])  # 루트 노드 찾을 때까지 재귀 호출
    return parent[x]

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

v, e = map(int, input().split())  # 노드 수, 간선 수 입력 받기
parent = [0] * (v+1)  # 부모 테이블 초기화

for i in range(1, v+1):  # 부모 테이블상에서 부모를 자기 자신으로 초기화
    parent[i] = i
    
cycle = False  # 사이클 발생 여부

for i in range(e):
    a, b = map(int, input().split())
    # 사이클이 발생한 경우
    if find_parent(parent, a) == find_parent(parent, b):
        cycle = True
        break  # 종료
    else:  # 사이클이 발생하지 않았다면
        union_parent(parent, a, b)  # union 연산 수행
        
if cycle:
    print("사이클이 발생했습니다.")
else:
    print("사이클이 발생하지 않았습니다.")

크루스칼 알고리즘

신장 트리 (Spanning tree)
: 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프. 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 함

크루스칼 알고리즘 (Kruskal Algorithm)
: 대표적인 최소 신장 트리 알고리즘. 이를 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있음.
먼저 모든 간선에 대하여 정렬을 수행한 뒤에 가장 거리가 짧은 간선부터 집합에 포함시키면 된다. 이때 사이클을 발생시킬 수 있는 간선의 경우, 집합에 포함시키지 않는다.

간선 데이터를 비용에 따라 오름차순으로 정렬한다.
간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
1) 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
2) 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.
모든 간선에 대하여 2번 과정을 반복한다.

def find_parent(parent, x):  # 특정 원소가 속한 집합 찾기
    if parent[x] != x:  # 루트 노드 아니라면
        parent[x] = find_parent(parent, parent[x])  # 루트 노드 찾을 때까지 재귀 호출
    return parent[x]

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

v, e = map(int, input().split())  # 노드 수, 간선 수 입력 받기
parent = [0] * (v+1)  # 부모 테이블 초기화

# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0

for i in range(1, v+1):  # 부모 테이블상에서 부모를 자기 자신으로 초기화
    parent[i] = i

for _ in range(e):  # 모든 간선에 대한 정보를 입력받기
    a, b, cost = map(int, input().split())
    # 비용 순으로 정렬하기 위해 튜플의 첫번쨰 원소를 비용으로 설정
    edges.append((cost, a, b))

edges.sort()  # 간선을 비용순으로 정렬

for edge in edges:  # 간선을 하나씩 확인
    cost, a, b = edge
    # 사이클이 발생하지 않은 경우에만
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)  # union 연산 수행 (집합에 포함)
        result += cost

print(result)

크루스칼 알고리즘 시간 복잡도

간선의 개수가 E개일 때, $O(ElogE)$ 의 시간 복잡도를 가짐
-> 크루스칼 알고리즘에서 시간이 가장 오래 걸리는 부분이 간선을 정렬하는 작업

위상 정렬

위상 정렬 (Topology Sort): 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'

알고리즘
1. 진입차수가 0인 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
1) 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

from collections import deque

v, e = map(int, input().split())  # 노드 수, 간선 수 입력 받기
indegree = [0] * (v+1)  # 모든 노드에 대한 집입차수는 0으로 초기화
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
graph = [[] for i in range(v+1)]

for _ in range(e):  # 방향 그래프의 모든 간선 정보를 입력받기
    a, b = map(int, input().split())
    graph[a].append(b)  # 정점 A에서 B로 이동 가능
    indegree[b] += 1  # 진입 차수 1 증가

def topology_sort():  # 위상 정렬 함수
    result = []  # 알고리즘 수행 결과를 담을 리스트
    q = deque()  # 큐 기능을 위한 deque 라이브러리 사용

    # 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
    for i in range(1, v+1):
        if indegree[i] == 0:
            q.append(i)

    while q:  # 큐가 빌 때까지 반복
        now = q.popleft()  # 큐에서 원소 꺼내기
        result.append(now)
        for i in graph[now]:  # 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
            indegree[i] -= 1
            if indegree[i] == 0:  # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
                q.append(i)

    for i in result:  # 위상 정렬을 수행한 결과 출력
        print(i, end=' ')

topology_sort()

위상 정렬 시간 복잡도

$O(V+E)$

실전문제

Ex1) 팀 결성

학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N+1개의 팀이 존재한다. 이때 선생님은 '팀 합치기' 연산과 '같은 팀 여부 확인' 연산을 사용할 수 있다.
1. '팀 합치기' 연산은 두 팀을 합치는 연산이다.
2. '같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다.
선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인' 연산에 대한 연산 결과를 출력하는 프로그램을 작성하시오.

입력조건
- 첫째 줄에 N, M이 주어진다. M은 입력으로 주어지는 연산의 개수이다. (1 $\leq$ N,M $\leq$ 100,000)
- 다음 M개의 줄에는 각각의 연산이 주어진다.
- '팀 합치기' 연산은 0 a b 형태로 주어진다. 이는 a번 학생이 속한 팀과 b번 학생이 속한 팀을 합친다는 의미이다.
- '같은 팀 여부 확인' 연산은 1 a b 형태로 주어진다. 이는 a번 학생과 b번 학생이 같은 팀에 속해 있는지를 확인하는 연산이다.
- a와 b는 N 이하의 양의 정수이다.

출력조건
- '같은 팀 여부 확인' 연산에 대하여 한 줄에 하나씩 YES 혹은 NO로 결과를 출력한다.

sol) 서로소 집합 알고리즘 문제
N,M의 범위가 모두 최대 100,000이므로 경로 압축 방식의 서로소 집합 자료구조 이용하여 시간 복잡도 계산

def find_parent(parent, x):  # 특정 원소가 속한 집합 찾기
    if parent[x] != x:  # 루트 노드 아니라면
        parent[x] = find_parent(parent, parent[x])  # 루트 노드 찾을 때까지 재귀 호출
    return parent[x]

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, m = map(int, input().split())
parent = [0] * (n+1)  # 부모 테이블 초기화

for i in range(1, n+1):  # 부모 테이블상에서 부모를 자기 자신으로 초기화
    parent[i] = i

for i in range(m):  # 각 연산을 하나씩 확인
    oper, a, b = map(int, input().split())
    if oper == 0:  # union 연산인 경우
        union_parent(parent, a, b)
    if oper == 1:  # find 연산인 경우
        if find_parent(parent, a) == find_parent(parent, b):
            print('YES')
        else:
            print('NO')

Ex2) 도시 분할 계획

동물원에서 막 탈출한 원숭이 한 마리가 세상 구경을 하고 있다. 어느 날 원숭이는 '평화로운 마을'에 잠시 머물렀는데 마침 마을 사람들은 도로 공사 문제로 머리를 맞대로 회의 중이었다.
마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 길마다 길을 유지하는데 드는 유지비가 있다.
마을의 이장은 마을을 2개의 분리된 마을로 분할할 계획을 세우고 있다. 마을이 너무 커서 론자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.
그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들을 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.

입력조건
- 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. (2 $\leq$ N $\leq$ 100,000 ,
1 $\leq$ M $\leq$ 1,000,000)
- 그다음 줄부터 M줄에 걸쳐 길의 정보가 A, B, C 3개의 정수로 공백으로 구분되어 주어지는데 A번 집과 B번 집을 연결하는 유지비가 C(1 $\leq$ C $\leq$ 1,000) 라는 뜻이다.

출력조건
- 첫째 줄에 길을 없애고 남은 유지비의 합의 최솟값을 출력한다.

sol) 전체 그래프에서 2개의 최소 비용 신장 트리를 만들어야함.
-> 크루스칼 알고리즘으로 최소 신장 트리를 찾은 뒤 최소 신장 트리를 구성하는 간선 중에서 가장 비용이 큰 간선을 제거함.
=> 이렇게 되면 최소 신장 트리가 2개의 부분 그래프로 나누어짐.

def find_parent(parent, x):  # 특정 원소가 속한 집합 찾기
    if parent[x] != x:  # 루트 노드 아니라면
        parent[x] = find_parent(parent, parent[x])  # 루트 노드 찾을 때까지 재귀 호출
    return parent[x]

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

v, e = map(int, input().split())  # 노드 수, 간선 수 입력 받기
parent = [0] * (v+1)  # 부모 테이블 초기화

# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0

for i in range(1, v+1):  # 부모 테이블상에서 부모를 자기 자신으로 초기화
    parent[i] = i

for _ in range(e):  # 모든 간선에 대한 정보를 입력받기
    a, b, cost = map(int, input().split())
    # 비용 순으로 정렬하기 위해 튜플의 첫번쨰 원소를 비용으로 설정
    edges.append((cost, a, b))

edges.sort()  # 간선을 비용순으로 정렬
last = 0  # 최소 신장 트리에 포함되는 간선 중 가장 비용이 큰 간선

for edge in edges:  # 간선을 하나씩 확인
    cost, a, b = edge
    # 사이클이 발생하지 않은 경우에만
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)  # union 연산 수행 (집합에 포함)
        result += cost
        last = cost

print(result - last)

Ex3) 커리큘럼

동빈이는 온라인으로 컴퓨터공학 강의를 듣고 있다. 이때 각 온라인 강의는 선수 강의가 있을 수 있는데, 선수 강의가 있는 강의는 선수 강의를 먼저 들어야만 해당 강의를 들을 수 있다. 예를 들어 '알고리즘' 강의의 선수 강의로 '자료구조'와 '컴퓨터 기초'가 존재한다면, '자료구조'와 '컴퓨터 기초'를 모두 들은 이후에 '알고리즘' 강의를 들을 수 있다.
동빈이는 총 N개의 강의를 듣고자 한다. 모든 강의는 1번부터 N번까지의 번호를 가진다. 또한 동시에 여러 개의 강의를 들을 수 있다고 가정한다. 예를 들어 N=3일 때, 3번 강의의 선수 강의로 1번과 2번 강의가 있고, 1번과 2번 강의는 선수 강의가 없다고 가정하자. 그리고 각 강의에 대하여 강의 시간이 다음과 같다고 가정하자.

1번 강의: 30시간
2번 강의: 20시간
3번 강의: 40시간

이 경우 1번 강의를 수강하기까지의 최소 시간은 30시간, 2번 강의를 수강하기까지의 최소 시간은 20시간, 3번 강의를 수강하기까지의 최소 시간은 70시간이다.
동빈이가 듣고자 하는 N개의 강의 정보가 주어졌을 때, N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 각각 출력하는 프로그램을 작성하시오.

입력조건
- 첫째 줄에 동빈이가 듣고자 하는 강의의 수 N (1 $\leq$ N $\leq$ 500)이 주어진다.
- 다음 N개의 줄에는 각 강의의 강의 시간과 그 강의를 듣기 위해 먼저 들어야하는 강의들의 번호가 자연수로 주어지며, 각 자연수는 공백으로 구분한다. 이때 강의 시간은 100,000 이하의 자연수이다.
- 각 강의 번호는 1부터 N까지로 구성되며, 각 줄은 -1로 끝난다.

출력조건
- N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 한 줄에 하나씩 출력한다 .

sol) 위상 정렬 알고리즘 사용
각 강의에 대하여 인접한 노드를 확인할 때, 인접한 노드에 대하여 현재보다 강의 시간이 더 긴 경우를 찾는다면, 더 오랜 시간이 걸리는 경우의 시간 값을 저장하는 방식으로 결과 테이블을 갱신하여 답을 구할 수 있음.
=> 위상 정렬을 수행하면서, 매번 간선 정보를 확인하여 결과 테이블 갱신

from collections import deque
import copy

v = int(input())  # 노드 개수 입력 받기
indegree = [0] * (v+1)  # 모든 노드에 대한 집입차수는 0으로 초기화
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
graph = [[] for i in range(v+1)]
time = [0] * (v+1)  # 각 강의 시간을 0으로 초기화

for i in range(1, v+1):  # 방향 그래프의 모든 간선 정보를 입력받기
    data = list(map(int, input().split()))
    time[i] = data[0]  # 첫번째 수는 시간 정보를 담고 있음
    for x in data[1:-1]:
        indegree[i] += 1
        graph[x].append(i)

def topology_sort():  # 위상 정렬 함수
    result = copy.deepcopy(time)  # 알고리즘 수행 결과를 담을 리스트
    q = deque()  # 큐 기능을 위한 deque 라이브러리 사용

    # 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
    for i in range(1, v+1):
        if indegree[i] == 0:
            q.append(i)

    while q:  # 큐가 빌 때까지 반복
        now = q.popleft()  # 큐에서 원소 꺼내기
        for i in graph[now]:  # 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
            result[i] = max(result[i], result[now] + time[i])
            indegree[i] -= 1
            if indegree[i] == 0:  # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
                q.append(i)

    for i in range(1, v+1):  # 위상 정렬을 수행한 결과 출력
        print(result[i])

topology_sort()

각 강의를 수강하기까지 최소 시간을 result 리스트에 담음
각 강의 시간은 time 리스트에 담겨있는데, 위상 정렬 함수 초기 부분에서 deepcopy() 함수
이용하여 time 리스트의 변수 값 복사하여 result 리스트 변수의 값으로 설정하는 작업이 수행.
리스트의 경우, 단순히 대입 연산을 하면 값이 변경될 때 문제가 발생할 수 있으므로 
리스트의 값을 복제해야할 때는 deepcopy() 함수 이용하자

기출문제

Q43 어두운 길

한 마을은 N개의 집과 M개의 도로로 구성되어 있습니다. 각 집은 0번부터 N-1번까지의 번호로 구분됩니다. 모든 도로에는 가로등이 구비되어 있는데, 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일합니다. 예를 들어 2번 집과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 해봅시다. 하루 동안 이 가로등을 켜기 위한 비용은 7이 됩니다.
정부에서는 일부 가로등을 비활성화하되, 마을에 있는 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록 만들고자 합니다. 결과적으로 일부 가로등을 비활성화하여 최대한 많은 금액을 절약하고자 합니다. 마을의 집과 도로 정보가 주어졌을 때, 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력하는 프로그램을 작성하세요.

입력조건
- 첫째 줄에는 집의 수 N (1 $\leq$ N $\leq$ 200,000)과 도로의 수 M (N-1 $\leq$ M $\leq$ 200,000)이 주어집니다.
- 다음 M개의 줄에 걸쳐서 각 도로에 대한 정보 X,Y,Z가 주어지며, 공백으로 구분합니다. (0 $\leq$ X,Y $<$ N) 이는 X번 집과 Y번 집 사이에 양방향 도로가 있으며, 그 길이가 Z라는 의미입니다. 단, X와 Y가 동일한 경우는 없으며, 마을을 구성하는 모든 도로의 길이 합은 $2^{31}$ 보다 작습니다.

출력조건
- 첫째 줄에 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력합니다.

sol) 가로등이 켜진 도로만을 이용해서, 모든 두 집이 서로 도달이 가능해야한다는 조건이 제시되어있음. 이때 최소한의 비용으로 모든 집을 연결해야 하기 때문에 최소 신장 트리 알고리즘 사용. (그래프에서 각 노드가 서로 연결되어 있는 연결 그래프와 같음)
=> 크루스칼 알고리즘 사용하여 '전체 가로등을 켜는 비용-최소 신장 트리 구성 비용'의 출력값을 구한다.

def find_parent(parent, x):  # 특정 원소가 속한 집합 찾기
    if parent[x] != x:  # 루트 노드 아니라면
        parent[x] = find_parent(parent, parent[x])  # 루트 노드 찾을 때까지 재귀 호출
    return parent[x]

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, m = map(int, input().split())  # 노드 수, 간선 수 입력 받기
parent = [0] * (n+1)  # 부모 테이블 초기화

# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0

for i in range(1, n+1):  # 부모 테이블상에서 부모를 자기 자신으로 초기화
    parent[i] = i

for _ in range(m):  # 모든 간선에 대한 정보를 입력받기
    x, y, z = map(int, input().split())
    # 비용 순으로 정렬하기 위해 튜플의 첫번쨰 원소를 비용으로 설정
    edges.append((z, x, y))

edges.sort()  # 간선을 비용순으로 정렬
total = 0  # 전체 가로등 비율

for edge in edges:  # 간선을 하나씩 확인
    cost, a, b = edge
    total += cost
    # 사이클이 발생하지 않은 경우에만
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)  # union 연산 수행 (집합에 포함)
        result += cost

print(total-result)

입력

출력