1. 서론

최근 "최소 스패닝 트리"에 대해 알게되고 해당 문제를 접하게 되었다.

당연히 그래프에서 사이클의 존재 여부를 파악하기 위해서는 DFS를 통해 전부 탐색해봐야지만 판단할 수 있다고 생각하고 있었다.

그러나 해당 포스트에서는 DFS보다 훨씬 간단하고, 적은 시간이 걸리는 서로소 집합을 통한 사이클 판별, 즉 부모 노드를 각 노드에 기록하는 방식으로 이를 해결하는 방법에 대해서 서술한다.

"이 포스트는 동빈나유튜브 채널을 참고 하였으며, 해당 채널에서 설명한 코드를 설명합니다. 언젠가 글쓴이가 생각한 방식에 대해서도 서술할 예정입니다."

2. 본론

1. 아이디어

각 노드별로 부모노드를 저장해놓고, 모든 노드 거쳐가면서 갱신해준다.

처음 각 부모노드는 자기 자신을 가리키며, 추후 갱신을 통해 특정 노드의 소속이 된다.

첫 포스트여서 굉장히 추상적이긴 하지만, 코드를 통해 이해할 수 있을 것이다.

2. 코드

함수

- find_parent()

- union_parent()

find_parent()함수의 역할은 다음과 같다.

- 자신의 부모 노드를 판별한다.

두 노드를 비교할 때 부모 노드가 다르다면 갱신해 줄 예정이라고 아이디어에서 설명하였다.
이때 매번 각 노드의 부모 노드를 갱신해준다면 노드의 수를 V라고 하였을 때, 매번 O(V)를 소모하게 된다.
나는 그렇게 짰다

따라서 해당노드의 부모노드는 백트래킹과 유사한(?) 방법을 사용한다.
자기 자신이 부모노드라고 칭하는 노드를 찾을 때까지 거슬러 올라가 발견시 부모노드를 리턴한다.

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

union_parent()함수의 역할은 다음과 같다.

- 부모노드를 합친다.

해당 함수는 간단하다.
find_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

메인함수에서는?

메인함수에서는 find_parent()를 통해
1. 부모노드가 같다면?
2. 그렇지 않다면?
두가지 경우로 나누어 원하는 작업을 수행하면된다.

3. 결론

해당 방식은 최소 스패팅 트리 문제에서 크루스칼 알고리즘을 구성할 때 사용한다. 추후 다른 알고리즘에도 사용한다면 갱신하도록 하겠다.

연관문제

1. 백준 1922 네트워크 연결

DFS가 아닌 새로운 방식이라는 점, 간단하면서도 시간복잡도를 크게 줄였다는 점에서 굉장히 좋은 코드라고 생각한다.
처음 포스팅을 결심하게 된 문제였고, 나와 같은 고민을 한 사람들이 있기를 바라며 해당 포스트를 작성하게 되었다.