[그래프 이론] 도시 분할 계획 (실전문제, 이것이 코딩테스트다 with 파이썬)

크루스칼 알고리즘

• 가장 적은 비용으로 모든 노드 연결
• 그리디 알고리즘

최소 신장 트리 알고리즘 : 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리 찾는 알고리즘

    - 대표적으로 크루스칼 알고리즘

    - ex) N개의 도시에서 전체 도시가 연결될 수 있게 도로 설치하는 경우

 

문제

 

해설

전체 그래프에서 2개의 최소 신장 트리 만드는 문제

1. 최소 신장 트리를 찾은 후
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:
        parnet[b] = a
    else:
        parent[a] = b

# 노드의 개수와 간선(union 연산)의 개수 입력받기
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)
        result += cost
        last = cost
        
print(result - last)

 

해석

변수 : 노드 개수 V, 간선 개수 E, 부모 테이블 parent, 간선 리스트 edges, 최종 비용 result, 비용 cost, 원소 a b, 비용 가장 큰 간선 last

함수 : 루트 노드 찾는 find_parent, 두 원소가 속한 집합 합치는 union_parent

 

* find_parent(부모 테이블 parent , 찾을 원소 x) : 최적화 ver, 루트 노드 찾음

ㄴ 루트 노드가 아니면 재귀적 호출 : (부모 노드 == 자기 자신) 이면 루트 노드

ㄴ return 루트 노드

 

* union_parent(부모 테이블 parent, 원소 a, 원소 b) : 두 원소가 속한 집합 합침

ㄴ a의 루트 노드 찾기 : find_parent

ㄴ b의 루트 노드 찾기 : find_parent

ㄴ 합치기 : 더 큰 루트 노드를 작은 루트 노드로 바꿈

 

1. 노드 개수 V, 간선 개수 E 입력받기

2. 부모 테이블 parent 초기화 : [0] * (v + 1)

3. 간선 리스트 edges, 최종 비용 result 초기화

4. 부모 테이블 parent 상에서 부모를 자기 자신으로 초기화

5. 간선 정보 입력받기 : edges.append((cost, a, b))    # 비용 순으로 정렬하고자, 첫 원소 비용 cost

6. 간선 edges 비용 순으로 정렬

-----------------------------------간선 개수만큼 반복문-----------------------------------

7. 사이클 판별 : find_parent

ㄴ a, b의 루트 노드가 달라 사이클 발생 X

ㅡㅡ union_parent : 합치기

ㅡㅡ result += cost  : 최종 비용 더하기

ㅡㅡ last = cost : 최소 신장 트리에 포함되는 간선 중 가장 비용이 큰 간선

--------------------------------------------------------------------------------------------------

8. 유지비 합의 최솟값 출력 : result - last