이코테 복습

그래프 이론

서로소 집합 알고리즘

parent = [i for i in range(n)]

# 경로가 필요한 경우
def find_parent(parent, x):
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return 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

크루스칼 알고리즘

• 최소 신장 트리 알고리즘 (모든 노드를 최소 비용으로 연결)

edges = [(cost, a, b) for _ in range(e) a, b, cost = map(int, iniput().split())]
edges.sort()

def kruskal(parent, edges):
    result = 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
    
    return result

위상 정렬 알고리즘

• 유향 그래프의 노드들을 방향성에 거스르지 않도록 정렬

from collections import deque

def topologySort(graph, indegree):
    result = []
    q = deque()
    
    for i in range(n):
        if indegree[i] == 0:
            q.append(i)
            
    while q:
        node = q.popleft()
        result.append(node)
        
        for i in graph[node]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)
                
    return result

팀 결성

• 0 ~ n 번호의 학생들, 같은팀인지 여부 확인시 YES, NO 출력

풀이특징

• 서로소집합 알고리즘 + 경로 압축 방법

n, m = map(int, input().split())
parent = [i for i in range(n+1)]

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

def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

for _ in range(m):
    unionCheck, a, b = map(int, input().split())
    if unionCheck == 1:
        a = find_parent(a)
        b = find_parent(b)
        print("YES" if a == b else "NO")
    else:
        union_parent(a, b)

도시 분할 계획

• n개의 집, m개의 양방향 길, 길의 유지비 존재
• 두 개의 분리된 마을로 분할, 마을 내 집들간의 경로는 존재해야 함, 길의 유지비의 최소값을 출력

풀이특징

• 크루스칼 알고리즘 + 경로 압축 방법 + 마지막 cost 제거

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
parent = [i for i in range(n)]
edges = []

for _ in range(m):
    a, b, cost = map(int, input().split())
    edges.append((cost, a-1, b-1))
    
edges.sort()

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

def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
    
result = 0
maxCost = 0
for edge in edges:
    cost, a, b = edge
    a = find_parent(a)
    b = find_parent(b)
    if a != b:
        union_parent(a, b)
        result += cost
        maxCost = cost
        
print(result - maxCost)