본 포스팅은 이것이 취업을 위한 코딩테스트다 - 나동빈 책을 통해 공부한 내용을 토대로 작성하였습니다.

🕰 복습 Time

그래프란 무엇일까요?

그래프란 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조를 의미합니다.

(서로 다른 개체가 연결되어있다 → '아 이건 그래프 알고리즘 😲☝️')

---

트리 자료구조 - 다양한 알고리즘에서 사용되므로 꼭 기억하자❗️
우선순위 큐 - 다익스트라 최단 경로 알고리즘에서 사용 (최소 힙, 최대 힙 이용)

그래프 vs 트리

• 그래프: 방향 그래프 or 무방향 그래프 / 순환 및 비순환 / 루트 노드 x / 부모-자식 관계 x / 네트워크 모델
• 트리: 방향 그래프 / 비순환 / 루트 노드가 존재 / 부모-자식 관계 / 계층 모델

그래프 구현 방법

1) 인접행렬(2차원 배열 사용)

메모리 공간: $O(V^2)$ , 간선비용 측정 시간: $O(1)$

ex) 플로이드 워셜

2) 인접리스트(리스트 사용)

메모리 공간: $O(E)$ , 간선비용 측정 시간: $O(V)$

---

유니온 파인드

✋ 서로소 집합

• 수학에서 서로소 집합이란 공통원소가 없는 두 집합을 말한다. ex) [1,2], [3,4]

• 서로소 집합 자료구조: 서로소 부분 집합들로 나누어진 원소들이 데이터를 처리하기 위한 자료구조
• 서로소 집합 자료구조는 union과 find 이 2개의 연산으로 조작할수 있다

✨ Union & Find으로 구성된 '서로소 집합 자료구조'

✔️ union(합집합) 연산 :2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산

✔️ find(찾기) 연산: 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

✨ 서로소 집합 자료구조의 구현

트리 자료구조를 이용하여 집합을 표현한다.

서로소 집합 정보(합집합 연산)가 주어졌을 때 트리 자료구조를 이용해서 집합을 표현하는 서로소 집합 계산 알고리즘은 다음과 같다. (union -> 두 노드가 같은 그룹이라는 의미이므로 그래프에서의 간선과 유사하다)

1️⃣ union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.

1) A와 B의 루트 노드 A', B'를 각각 찾는다.

2) A'를 B'의 부모 노드로 설정한다. (B'가 A'를 가리키도록 한다.)

2️⃣ 모든 union 연산을 처리할 때까지 1️⃣ 과정을 반복한다.

✨ 예시)

입력

전체집합: [1,2,3,4,5,6]

주어진 4개의 union연산:

• union 1, 4

  1과 4는 같은 집합, 그래프 형태로 해석하면 노드1과 노드 4를 연결하는 간선이 존재한다고 볼 수 있다.

• union 2, 3

• union 2, 4

• union 5, 6

union연산을 그래프로 나타낸 결과:

👉 보통 번호가 큰 노드가 번호가 작은 노드를 가리키도록 트리를 만든다.

무튼 그림을 통해 전체 원소가 [1,2,3,4]와 [5,6]이라는 두 집합으로 나누어지는 것을 알 수 있다! 이렇게 union연산을 토대로 그래프를 그리면 '연결성'으로 손쉽게 집합의 형태를 확인할 수 있다.

✨ 소스코드

• source

    # x의 부모 노드를 알아내는 함수 (특정원소가 속한 집합을 찾기)
    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

    for i in range(e):
    	a, b = map(int, input().split())
    	union_parent(parent, a, b)

각 원소가 속한 집합을 알기위해서는 반복문을 수행하여 parent배열에 대해 find_parent(parent, i)를 출력한다.

---

✨ 경로 압축 기법

하지만, 위 같은 경우 find 함수가 비효율적으로 동작해서 최악의 경우 find함수가 모든 노드를 다 확인하느라 시간복잡도가 O(V)가 될 수 도 있다.

그래서 어떻게 해결? 경로 압축 기법 적용하면 시간복잡도를 개선시킬 수 있음!

경로 압축: find 함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 갱신하는 기법

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

각 노드에 대하여 find 함수를 호출한 이후에, 해당 노드의 루트 노드가 바로 부모 노드가 된다!

✨ 서로소 집합 알고리즘의 시간복잡도

경로 압축 방법만을 이용할 경우

노드 개수 V개, 최대 V - 1개의 union연산, M개의 find 연산이 가능한 경우

👉 $O(V+M(1+log \scriptscriptstyle 2-M/V \normalsize V ))$

• 서로소 집합을 활용한 사이클 판별: 루트노드가 서로 같다면 사이틀이 발생한 것