💭크루스칼 알고리즘

이번 주차 모든 문제가 최소 신장 트리(크루스칼 알고리즘)을 활용하는 것이여서
우선 알고리즘을 풀기 위해 내가 간단히 이해한 크루스칼 알고리즘에 대해 간단히 두가지로 나누어 설명해보자면

❓크루스칼 알고리즘이 필요한 경우

가중치가 존재하는 그래프에서 신장 트리(=모든 노드를 포함해 연결되면서 사이클이 존재하지 않는=트리)를 최소한의 비용으로 찾아야 할 때 크루스칼 알고리즘을 쓴다.

🤔그러면 우리는 어떤 문제를 만났을 때 크루스칼 알고리즘을 떠올려야 하는가??
1. 그래프와 비슷한 모양새(간선과 노드가 존재) 일때
2. 최소한의 비용, 혹은 사이클이 존재하지 않되 모두가 연결되어야 함을 요구할 때

❗크루스칼 알고리즘의 단계

1. 간선 가중치를 오름차순으로 정렬
2. 간선을 순서대로 확인, 현재의 간선이 사이클을 발생시키는지 확인
3. 사이클이 발생 안되면 답에 포함, 발생하는 경우 포함하지 않음 (이를 모든 간선에 대하여 반복한다.)

#1922 네트워크 연결

문제

🔗https://www.acmicpc.net/problem/1922

해당 알고리즘을 이해하는 건 어렵지 않았는데, 그걸 코드로 구현하는게 꽤 복잡하다고 느꼈다.
-> (이것 때문에 실버인 문제를 찾는게 어려웠던 것 같기도 하고)
이해를 위해 나는 곧바로 예제 코드를 봐버려서 예제와 같은 방식으로 풀었긴 하지만 맨땅에 헤딩으로 풀었다면 많이 헤맸을 것 같다. (특히 사이클을 발생시키는지 확인하는 기능 구현😅😅)

코드

import sys

#해당 간선이 사이클을 발생시키는지 확인하기 위해 실행하는 함수
#parent배열을 통해 x의 부모를 재귀적으로 찾는 함수
def find_parent(parent, x):
    if parent[x]!=x:
        parent[x] = find_parent(parent,parent[x])
    return parent[x]
    
#사이클이 발생되지 않아, 최소신장트리에 해당 간선 포함할 때 실행하는 함수
#parent배열을 업데이트 시켜 해당 노드의 부모 노드를 저장하는 함수 
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=int(sys.stdin.readline().rstrip())
#간선의 수
e=int(sys.stdin.readline().rstrip())

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, sys.stdin.readline().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)
        #result에 cost(가중치)를 더해줌으로써 최소비용을 업데이트 시킨다.
        result+=cost

print(result)

#9372 상근이의 여행

문제

🔗https://www.acmicpc.net/problem/9372

해당 문제는 간선의 가중치가 존재하지 않으니 크루스칼 알고리즘 단계 중 <간선을 오름차순으로 정렬하는 단계>를 생략했다.

코드

import sys

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

T=int(sys.stdin.readline().rstrip())

#테스트케이스만큼 반복
for i in range(T):

    #노드의 수, 간선의 수
    v,e=map(int,sys.stdin.readline().split())

    parent=[0]*(v+1)

    edges=[]
    result=0

    for i in range(1,v+1):
        parent[i]=i

    for _ in range(e):
        a,b=map(int, sys.stdin.readline().split())
        edges.append((a,b))

    for edge in edges:
        a,b=edge
        if find_parent(parent,a)!=find_parent(parent,b):
            union_parent(parent,a,b)
            result+=1

    print(result)

#1197 최소 스패닝 트리

문제

🔗https://www.acmicpc.net/problem/1197

해당 문제가 예제와 완전히 동일했던 문제인 것 같다...

코드

import sys

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,sys.stdin.readline().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, sys.stdin.readline().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)
        result+=cost

print(result)