<PART 2>그래프이론 (서로소 집합)

그래프: 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조

DFS/BFS, 최단경로 알고리즘에서 다룬 내용은 모두 그래프 알고리즘의 한 유형이라고 생각할 수 있습니다.
즉, 여기서 다룰 알고리즘은 앞서 배운 내용에 기반한 내용입니다.
크루스칼 알고리즘은 그리디 알고리즘으로 분류되며, 위상 정렬 알고리즘은 앞서 배운 큐 자료구조 혹은 스택 자료구조를 활용해야 구현할 수 있습니다.
알고리즘 문제에 접했을 때 서로 다른 개체(혹은 개체)가 연결되어 있다는 이야기를 들으면 가장 먼저 그래프 알고리즘을 떠올려야 합니다. 예를 들어 '여러 개의 도시가 연결되어 있다'와 같은 내용이 등장하면 그래프 알고리즘을 의심해야 합니다.

그래프 자료구조 중에 트리 자료구조는 다양한 알고리즘에서 사용되므로 꼭 기억해야 합니다.
'다익스트라 최단경로 알고리즘' : 우선순위 큐 -> 최소 힙 or 최대 힙
여기서 최소 힙은 항상 부모 노드가 자식 노드보다 크기가 작은 자료구조로서 트리 자료구조에 속합니다. 트리 자료구조는 부모에서 자식으로 내려오는 계층적인 모델에 속합니다.
다음은 그래프와 트리 자료구조를 비교한 표입니다.

	그래프	트리
방향성	방향 그래프 혹은 무방향 그래프	방향 그래프
순환성	순환 및 비순환	비순환
루트 노드 존재 여부	루트 노드가 없음	루트 노드가 존재
노드간 관계성	부모와 자식 관계없음	부모와 자식 관계
모델의 종류	네트워크 모델	계층 모델

또한, 그래프 알고리즘에서는
- 인접 행렬: 2차원 배열을 사용하는 방식
- 인접 리스트: 리스트를 사용하는 방식

2가지 모두 그래프 알고리즘에서 매우 많이 사용됩니다. 두 방식은 메모리와 속도 측면에서 구별되는 특징을 가집니다.

1. 다익스트라 최단 경로 알고리즘: 우선순위 큐 이용 -> 인접 리스트를 이용하는 방식
(노드의 개수가 V개 일 때는 V개의 리스트를 만들어서 각 노드와 연결된 모든 간선에 대한 정보를 리스트에 저장)

2. 플루이드 워셜 알고리즘: 인접 행렬을 이용하는 방식
(모든 노드에 대하여 다른 노드로 가는 최소비용을 V^2크기의 2차원 리스트에 저장한 뒤에 해당 비용을 갱신해서 최단 거리를 계산)
=> 노드의 개수가 적은 경우-> 플루이드 워셜 알고리즘
=> 노드와 간선의 개수 모두 많은 경우 -> 우선순위 큐를 이용하는 다익스트라 알고리즘

- 서로소 집합
서로소 집합: 공통 원소가 없는 두 집합
ex) {1,2}와 {3,4}는 서로소 관계입니다.

서로소 집합 자료구조는 몇몇 그래프 알고리즘에서 매우 중요하게 사용되며, union과 find 이 2개의 연산으로 조작할 수 있습니다.
union 연산: 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
find: 연산: 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
스택과 큐가 push와 pop연산으로 이루어졌던 것처럼, 서로소 집합 자료구조는 union(합집합)과 find(찾기) 연산으로 구성됩니다.

-서로소 집합 자료구조
서로소 집합 자료구조를 구현할 때는 트리 자료구조를 이용하여 집합을 표현합니다. 

1. union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인합니다.
1-1) A와 B 루트 노드 A',B'를 각각 찾습니다.
1-2) A'를 B'의 부모 노드로 설정합니다.(B'가 A'를 가리키도록 합니다.)

2. 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반복합니다.

위 그림과 같이 이 알고리즘에서 유의할 점은 union연산을 효과적으로 수행하기 위해 '부모 테이블'을 항상 가지고 있어야 한다는 점입니다.
이때, 초기에 자기 자신을 부모로 가지는 테이블을 가져야 합니다.
또한, 루트 노드를 즉시 계산할 수 없고 부모 테이블을 계속 확인하며 거슬러 올라가야 합니다.
예를 들어 노드 5의 부모노드는 4라고 되어 있지만 최종적으로는 노드 5의 루트 노드는 6이라고 볼 수 있습니다.
결과적으로, 서로소 집합 알고리즘으로 루트를 찾기 위해서는 재귀적으로 부모를 거슬러 올라가야 한다는 점이 중요합니다.
기본적인 서로소의 집합 알고리즘의 소스코드는 다음과 같습니다.

입력 예시)
6 4
1 4
2 3
2 4
5 6

출력 예시)

#특정 원소가 속한 집합을 찾기
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
 
#노드의 개수와 간선(union 연산)의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1) #부모 테이블 초기화
 
#부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v+1):
    parent[i] = i
 
#union 연산을 각각 수행
for i in range(e):
    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=' ')

1. union 연산과 find 연산을 위한 함수를 생성합니다.
2. union 연산을 할 경우, 같은 집합에 속한 원소를 작은 숫자가 부모 노드가 되도록 합칩니다.
3. find 연산을 할 경우,  자신의 부모노드를 찾을 때까지 재귀적으로 거슬러 오릅니다.
4. 노드의 개수와 간선 개수(union 연산의 횟수)를 입력받습니다.
5. 부모 테이블을 항상 가지고 있어야 하므로 노드의 개수만큼 부모 테이블을 자기 자신으로 초기화 시킵니다.
6.  union 연산으로 간선의 갯수만큼 같은 집합에 속한 원소의 부모 노드를 설정해줍니다.
7. find 연산을 통해 각 원소가의 루트 노드를 출력합니다.
8. 루트노드가 아닌 자신의 부모 노드를 출력합니다.

ex)
1 4
2 3
2 4 의 연산을 할 때
2 4가 1개의 집합이므로 2의 루트노드가 1이 된다. 그리고 3은 2와 같은 집합이므로 부모테이블 상으로는 2지만, 루트 노드는 1이 됩니다.

이와 같이 부모 노드와  루트 노드가 일치하는 않는 경우, find 연산 함수가 비효율적으로 작용하게 될 수도 있습니다.
그래서 이러한 find 함수는 아주 간단한 과정으로 최적화를 시키게 됩니다. 바로 경로 압축 기법을 적용하면 시간 복잡도를 개선 시킬 수 있습니다.
경로 압축: 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
 
#노드의 개수와 간선(union 연산)의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1) #부모 테이블 초기화
 
#부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v+1):
    parent[i] = i
 
#union 연산을 각각 수행
for i in range(e):
    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=' ')

출력)

이처럼 경로 압축 기법을 이용하게 되면 루트 노드에 더욱 빠르게 접근할 수 있다는 점에서 기존의 기본적인 알고리즘과 비교했을 때 시간 복잡도가 개선됩니다.

- 서로소 집합을 활용한 사이클 판별
서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다는 특징이 있습니다.
앞에 설명한 union 연산은 그래프에서의 간선으로 표현될 수 있습니다. 따라서 간선을 하나씩 확인하면서 두 노드가 포함되어 있는 집합을 합치는 과정을 반복하는 것만으로도 사이클을 판별할 수 있습니다.

1. 각 간선을 확인하며 두 노드의 루트 노드를 확인합니다.
1-1) 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행합니다.
1-2) 루트 노드가 서로 같다면 사이클이 발생한 것입니다.

2. 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복합니다.

이와 같이 초기화를 한 후에 간선(1,2), (1,3)이라면 각각의 루트 노드는 1이 됩니다.
이후 (2,3)간선이 있다면, 노드 2와 노드 3은 이미 루트 노드로 '노드 1'을 가지고 있으므로 사이클이 발생한다는 것을 알 수 있습니다.
이러한 사이클 판별 알고리즘은 그래프에 포함되어 있는 간선의 개수가 E개 일때 모든 간선을 하나씩 확인하며, 매 간선에 대하여 union 및 find 함수를 호출하는 방식으로 동작합니다. 이 알고리즘은 간선에 방향성이 없는 무향 그래프에서만 적용 가능합니다.

입력 예시)
3 3
1 2
1 3
2 3

출력 예시)
사이클이 발생했습니다.

- 서로소 집합을 활용한 사이클 판별 소스코드

#특정 원소가 속한 집합을 찾기
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
 
#노드의 개수와 간선(union 연산)의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1) #부모 테이블 초기화
 
#부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v+1):
    parent[i] = i
 
cycle = False #사이클 발생 여부
 
#union 연산을 각각 수행
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)
 
if cycle:
    print("사이클이 발생했습니다.")
 
else:
    print("사이클이 발생하지 않았습니다.")