CS/알고리즘, 자료구조

[알고리즘 특강 6일차] 서로소 집합, 위상정렬, 최소 신장 트리, 최소 공통 조상 (Disjoint Set, Union-Find, DAG; Directed Acyclic Graph, Topological Sort, MST; Minimum Spanning Tree, Kruskal, Prim, LCA; Lowest Common Ancestor)

always-dev 2022. 7. 25.

최소 신장 트리 (MST; Minimum Spanning Tree)

트리란? (Tree)

무향 그래프 G가 순환 없는 연결 그래프이면 G는 트리입니다.

숲이란? (Forest)

무향 그래프 G가 순환이 없는 그래프이면 G는 숲입니다.

신장 트리란? (Spanning Tree)

무향 연결 그래프 G의 부분그래프이며, G의 모든 정점을 포함 트리인 그래프입니다.

무향 연결 가중 그래프 S에서 간선의 가중치의 합이 최소인 신장 트리 (Spanning Tree) 입니다.

때문에 최소 신장 트리의 답은 여러 개가 될 수 있습니다.

신장 트리 탐색 종류

DFS Spanning Tree
BFS Spanning Tree
크루스칼 알고리즘 (Kruskal)
프림 알고리즘 (Prim)

크루스칼 알고리즘 (Kruskal)

크루스칼은 간선을 기준으로 두고 있습니다.
DisjointSet를 응용하여 풀 수 있습니다
주어진 간선을 오름차순으로 정렬하고 양끝단 사이클을 검사하며 간선을 따라가주면 됩니다.
시간 복잡도는 $O(ElogE)$입니다.

크루스칼 문제

1922번: 네트워크 연결

이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다.

www.acmicpc.net

크루스칼 느낌

Collections.sort(adj, Comparator.comparingInt(Route::getC));
		
		int answer = 0; // 최소 비용 합
		for (Route curr : adj) {
			if (isSameParent(curr.a, curr.b) == false) {
				union(curr.a, curr.b);
				answer += curr.c;
			}
		}
	
	static void union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		
		if (aRoot == bRoot) return;
		
		parent[bRoot] = aRoot;
	}
	
	static int find(int a) {
		if (parent[a] == a) return a;
		else return parent[a] = find(parent[a]);
	}
	
	static boolean isSameParent(int a, int b) {
		if (find(a) == find(b)) return true;
		else return false;
	}

프림 알고리즘 (Prim)

프림은 ‘정점'을 기준으로 두고 있습니다.
visitied[]로 사이클을 해결합니다.
최소힙을 이용하여 간선들을 꺼내서 만들어줍니다.
시간복잡도는 $O(ElogV)$ 입니다.

프림 느낌

queue.add(1);
int answer = 0;
while (!queue.isEmpty()) {
	Route curr = queue.poll();
	
	if (visited[curr.b] == false) {
		visited[curr.b] = true;
		answer += curr.c
		for (int next : adj[curr]) {
			queue.add(next);
		}
	}
}

위상정렬 (Topological Sort)

DAG (Directed Acyclic Graph)

DAG는 순환을 가지지 않는 방향 그래프입니다.
일반적으로 우선순위를 가진 일련의 작업들은 DAG 구조를 갖습니다.

위상정렬

DAG에서 그래프의 방향성을 거스르지 않고 정점들을 나열하는 것입니다.
위상정렬은 각 정점을 우선순위에 따라 배치한 것입니다.
위상정렬의 결과는 유일하지 않습니다.

위상정렬 순서 알아내는 방법

indegree (진입차수)를 이용하여 문제를 풉니다.

주어진 그래프에서 indegree가 0인 정점은 선행자가 없으므로 첫 정점입니다.

정점을 제거하면서 연관된 정점의 indegree들을 -1씩 합니다.

다시 indegree가 0인 정점을 제거하고 연관 정점의 indegree -= 1합니다.

계속 반복해서 제거되는 순서를 이용합니다.

진입 차수 배열 만드는 방법

입력 값으로 방향이 있는 간선이 들어온다고 하겠습니다.

(u, v)가 들어왔을 때

static boolean[] visited;
static int[] inDegree = new int[N + 1];

for (;;) {
	StringTokenizer st = new StringTokenizer(br.readLine());
	int u = Integer.parseInt(st.nextToken());
	int v = Integer.parseInt(st.nextToken());

	inDegree[v]++; // 진입 차수 증가
}

진입 차수를 이용해서 위상 정렬 하기

Queue<Integer> queue = new LinkedList<>();

for (int i = 1; i <= N; i++) {
	for (int next : adj[i]) {
		inDegree[next] -= 1;
		if (inDegree[next] == 0) {
			queue.add(next);
		}
	}
}

최소 공통 조상 (LCA; Lowest Common Ancestor)

트리 그래프가 있다고 했을 때 정점 A와 정점 B가 각각 자신을 포함하여 조상을 따라 거슬러 올라갈 때

“**처음 공통으로 만나게 되는 정점”**을 LCA라고 합니다.

DFS와 BFS

LCA는 DFS, BFS 둘 다 구할 수 있습니다.

최상위 조상 정점을 시작으로 DFS(or BFS)를 수행하여 각 정점의 깊이와 부모 정점을 저장합니다.
1. parent[][]
2. depth[]
정점의 부모를 따라 하나씩 올라가 LCA를 찾습니다.

LCA 빠르게 구하기 (점프하기)

만약 정점 A와 정점 B가 있다고 할 때

정점 A의 깊이는 12

정점 B의 깊이는 3이라고 하면

정점 A는 깊이 3으로 점프하여 좀 더 빠르게 LCA를 구할 수 있습니다.

이때 점프하기 위해서는 다음과 같은 것들을 알고 있어야합니다.

parent[K][V]
- 정점 V의 2^k번째 조상 정점 번호
depth[]
- 각 정점의 깊이

또한 조상 정점에 대한 배열은 다음과 같은 식이 성립합니다.

parent[K][V] = parent[k - 1[parent[k - 1][V]]

이 식에 대한 예시를 들자면 다음과 같습니다.

정점 3의 4번 째 조상 정점 번호는

정점 (3의 2번 째 조상 정점 번호) 의 2번째 번호와 같습니다.

그러면 이것을 어떤 식으로 이용할까요 ?

정점 A와 정점 B가 있다고 할 때 두 깊이를 비교합니다.
정점 A의 깊이가 깊었을 때
int gap = depth[A] - depth[B]를 만들어
gap을 2진수로 만들어 1이 있는 만큼 정점 A를 위로 올라가게 합니다.
만약 gap이 7이라면 111(2)로 정점 A를 2^0 만큼 올리고 2^1만큼 올리고 2^2만큼 올리면 depth[A] == depth[B]가 됩니다.

이제 parent를 사용해줍니다.

먼저 루트 이상으로 정점A와 정점B를 이동시켜줍니다.
정점A의 2^k번째 조상 번호와 정점B의 2^k번째 조상 번호가 같지 않다면
정점A의 2^k 번째 이하의 정점은 모두 정점B와 공통 조상이 존재할 수 없습니다.
때문에 그 위로는 공통 조상이 또 있을 수 있어서 탐색해줘야합니다.

시간복잡도

트리의 깊이를 H라고 할 때,

시간복잡도는 $O(logH)$

최악의 경우 $O(logN)$

LCA 이용하는 문제

11438번: LCA 2

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정