해당 문제는 "이것이 코딩 테스트이다" 책을 참고하여 제작하였습니다.
크루스칼 알고리즘 사용시 findParent 마지막에 한번 더 돌려줄 것.
그래프 알고리즘의 종류
- DFS/BFS (큐, 재귀함수)
- 다익스트라 (우선순위 큐(최소 힙, 최대 힙))
- 크루이드 워셜 (삼중 반복문)
- 크루스칼 알고리즘 (그리디 알고리즘으로 분류)
- 위상 정렬 알고리즘 (큐, 스택 자료구조로 분류)
최소 힙, 최대 힙 - 트리 구조로서 부모노드가 자식노드보다 크거나 작거나 한 구조
그래프 vs 트리
- 그래프
방향성 : 방향 그래프 or 무방향 그래프
순환성 : 순환 or 비순환
루트 노드 : 없음
부모 자식 관계성 : 없음
모델 : 네트워크 모델
- 트리
방향성 : 방향 그래프
순환성 : 비순환
루트 노드 : 있음
부모 자식 관계성 : 있음
모델 : 계층 모델
입접행렬 vs 인접리스트
- 인접행렬 (플로이드 워셜 알고리즘이 사용)
간선 저장 : N**2
비용 확인 : 1
- 인접 리스트 (다익스트라 알고리즘이 사용)
간선 저장 : E
비용 확인 : N
1. 서로소 집합 알고리즘
서로소 집합 : 공토 원소가 없는 두 집합
서로소 집합 알고리즘 : 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
이용
- 그래프의 연결성(서로 같은 집합에 속하는지 아닌지) 확인
연산
- union 연산 : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산, 합집합
- find 연산 : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
자료구조
- 트리 자료구조 이용
로직
1. union연산을 확인하여 서로 연결된 두 노드 A,B를 확인한다.
1-1. A와 B의 루트 노드 A', B'를 찾는다
1-2. A'를 B'의 부모 노드로 설정한다.(B'가 A'를 가리키도록 한다.)
2. 모든 union 연산을 처리할때까지 반복
- 원소 번호가 작은 노드가 부모 노드가 되도록 구현하여 트리구조로 구현
기본 코드 (JAVA)
public static void main(String[] args){
int[][] data = {{1, 4}, {2, 3}, {2, 4}, {5, 6}};
int[] root = {0, 1, 2, 3, 4, 5, 6};
for(int[] now : data){
int parent1 = find_parent(now[0] ,root);
int parent2 = find_parent(now[1] ,root);
if(parent1 > parent2){
root[parent1] = parent2;
}
else{
root[parent2] = parent1;
}
}
}
public static int find_parent(int x, int[] root){
if(x != root[x]){
x = find_parent(root[x], root);
}
return x;
}
문제점
- find_parent 연산의 비효율성 : 만약 1, 2, 3, 4, 5, 6 순으로 n의 부모는 n-1일때, 시간복잡도가 N과 같다.
- 전체 시간복잡도는 간선(E) x find_parent(N) 일 때, 최악시 NE 가 됨.
경로 압축 기법
public static int find_parent(int x, int[] root){
if(x != root[x]){
return find_parent(root[x], root);
}
return x;
}
public static int new_find_parent(int x, int[] root){
if(root[x] != x){
root[x] = find_parent(root[x], root);
}
return root[x];
}
예를 들어 [1, 1, 2, 3, 4] 라는 결과가 있다.
이들을 서로소 집합으로 묶을 것이다.
기존의 방법은 아래와 같은 방식으로 동작한다.
5의 부모노드 : 4 -> 3 -> 2 -> 1
4의 부모노드 : 3 -> 2 -> 1
경로 압축 기법 사용시 동작은 아래와 같다.
5의 부모 노드 : 4 -> 3 -> 2 -> 1
4의 부모노드 : 1
3의 부모노드 : 1
2의 부모노드 : 1
10회의 연산 -> 7회의 연산
즉, 5의 부모노드를 처리할 때 다른 노드의 부모노드까지 처리해준다.
사이클 판별
- 서로소 집합은 무방향 그래프 내에서 사이클을 판별할 때 사용 가능하다.
- 방향 그래프에서는 사이클 여부를 DFS로 판단
로직
1. 간서을 확인하며 두 노드의 루트노드를 확인한다.
1-1. 루트 노드가 다르면 두 노드에 대하여 union 연산을 수행
1-2. 루트 노드가 서로 같다면 사이클이 발생한 것이다.
2. 모든 간선 확인
모든 노드의 루트노드가 같아 사이클이 발생한경우를 판별하는 코드
public class Cycle {
public static void main(String[] args){
int[][] lines = {{1, 2}, {1, 3}, {2, 3}};
int[] parents = {0, 1, 2, 3};
for(int[] line : lines){
int parent1 = find_parent(parents, line[0]);
int parent2 = find_parent(parents, line[1]);
if(parent1 > parent2){
parents[parent1] = parent2;
}
else if(parent1 == parent2){
System.out.println("사이클 발생");
}
else{
parents[parent2] = parent1;
}
}
}
private static int find_parent(int[] parents, int node){
if(parents[node] != node){
parents[node] = find_parent(parents, parents[node]);
}
return parents[node];
}
}
신장 트리
- 하나의 그래프가 있을 때 모든 노드를 연결하면서 사이클이 존재하지 않는 부분 그래프
조건1 : 모든 노드를 연결한다.
조건2 : 사이클이 존재하지 않는다.
2. 크루스칼 알고리즘
이용
- 최소 신장 트리 알고리즘을 구현
(-> 모든 노드를 연결하되 최소한의 비용으로 연결하는 알고리즘)
- 가장 적은 비용으로 모든 노드를 연결한다.
- 같은 그룹의 노드들, 노드들을 연결한 간선이 있을 때, 선 하나를 끊으면 그룹이 두개로 분리
로직
1. 간선을 비용에 따라 오름차순 정렬
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
2-1. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함 (서로소 집합 알고리즘 수행)
2-2. 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.
3. 모든 간선 확인
"결과적으로 최소 신장 트리에 포함되는 간선의 개수가 노드의 개수 - 1이 된다."
예시 코드
public class Kruskal {
public static void main(String[] args){
int[][] lines = {
{29, 1, 2}, {35, 2, 3}, {7, 3, 4}, {13, 4, 7},
{23, 4, 6}, {25, 6, 7}, {34, 2, 6}, {53, 5, 6},
{75, 1, 5}
};
int[] parents = {0, 1, 2, 3, 4, 5, 6, 7};
int result = 0;
Arrays.sort(lines, Comparator.comparingInt(arr -> arr[0]));
for(int[] line : lines){
int parent1 = find_parent(parents, line[1]);
int parent2 = find_parent(parents, line[2]);
if(parent1 != parent2){
parents[parent1] = (parent1 > parent2) ? parent2 : parent1;
parents[parent2] = (parent1 > parent2) ? parent2 : parent1;
result += line[0];
}
}
System.out.println(result);
}
public static int find_parent(int[] parents, int node){
if(node != parents[node]){
parents[node] = find_parent(parents, parents[node]);
}
return parents[node];
}
}
시간 복잡도
- 크루스칼알고리즘의 시간 복잡도에 영향을 끼치는 요소는 간선을 정렬하는 과정, 서로소 집합 알고리즘 정도이다.
하지만 서로소 집합 알고리즘의 시간복잡도는 굉장히 정렬 알고리즘에 비해 작기에
정렬 알고리즘만 고려하면 O(ElogE) 정도이다.
3. 위상 정렬
- 정렬 알고리즘의 일종
- 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것
- 그래프 상, 노드 간 선후 관계 존재시 위상정렬을 수행하여 선후 관계를 지키는 전체 순서를 계산가능.
로직
1. 진입 차수가 0인 노드를 큐에 넣는다.
2. 큐가 빌때까지 밑의 과정을 반복
2-1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
2-2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
(+)
- 진입 차수 : 특정한 노드로 들어오는 간선의 개수
- 만약, 모든 노드를 방문하기 전에 위의 로직이 종료된다면 사이클이 발생한 것으로 판단.
기본 코드
import java.util.*;
public class TopologySort {
public static void main(String[] args){
int[][] lines = {{1, 2}, {1, 5}, {2, 3}, {2, 6}, {3, 4}, {4, 7}, {5, 6}, {6, 4}};
List<List<Integer>> map = new ArrayList<>();
int[] indegree = new int[8];
for(int i=0; i<8; i++){
List<Integer> test_map = new ArrayList<>();
map.add(test_map);
indegree[i] = 0;
}
for(int[] line : lines){
map.get(line[0]).add(line[1]);
indegree[line[1]] += 1;
}
System.out.println(map);
for(int i : indegree){
System.out.print(i);
}
System.out.println(" ");
List<Integer> queue = new ArrayList<>();
for(int i=1 ; i<indegree.length; i++){
if(indegree[i] == 0){
queue.add(i);
}
}
System.out.println(queue);
List<Integer> answer = new ArrayList<>();
while(queue.size() > 0){
int now_node = queue.remove(0);
answer.add(now_node);
for(int i : map.get(now_node)){
indegree[i] -= 1;
if(indegree[i] == 0){
queue.add(i);
}
}
}
}
}
시간 복잡도
- O(N + E) : 모든 노드 확인, 모든 간선 제거
