그래프
노드와 노드사이에 연결된 간선의 정보를 가지고 있는 자료구조
ex ) 여러개의 도시가 연결되어 있다
그래프 구현 방법
- 인접 행렬 : 2차원 배열을 사용
- 인접 리스트 : 리스트를 사용
두가지 방식 특징 ( 노드의 갯수 V, 간선의 갯수 E인 그래프)
인접 행렬 이용
- 장점 - 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용을 $O(1)$의 시간으로 즉시 알수 있음
- 단점 - 간선 정보를 저장하기 위해 $O(V^2)$ 만큼의 메모리 공간이 필요
인접 리스트 이용
- 장점 - $O(V)$만큼의 시간 소요
- 단점 - 간선의 개수만큼 $O(E)$만큼의 메모리 공간 필요
서로소 집합 (유니온 파인드 - Union find)
공통 원소가 없는 두 집합
union - 합집합 연산 - 2개의 원소가 포함된 집합을 하나의 집합으로 합침
find - 찾기 연산 - 특정 원소가 속한 집합이 어떤 집합인지 알려줌
트리 자료 구조 이용
- union(합집합) 연산을 확인하여, 서로 연결된 두 노두 A,B 확인
- A와 B의 루트 노드 A', B'를 찾음
- A'를 B'의 부모 노드로 설정
- 모든 union(합집합) 연산을 처리할 때까지 1번 과정 반복
(A', B' 중 보통 더 작은 숫자가 부모가 됨)
#include <stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <deque>
#include <stack>
#include <vector>
#include<cstdio>
#include<algorithm>
#include<memory.h>
#include<queue>
#include<map>
#define MAX 100001
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정
using namespace std;
int parent[MAX];
int V, E;
int findParent(int num) {
if (num == parent[num]) return num;
findParent(parent[num]);
}
void func(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a > b) parent[a] = b;
else parent[b] = a;
}
int main(void) {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin >> V >> E;
for (int i = 1; i <= V; i++) {
parent[i] = i;
}
for (int i = 0; i < E; i++) {
int a, b;
cin >> a >> b;
func(a, b);
}
// 각원소가 속한 최상위 집합
int cnt = 0;
for (int i = 1; i <= V; i++) {
cout << findParent(i) << " ";
}
cout << "\n";
// 각원소의 부모 테이블
for (int i = 1; i <= V; i++) {
cout << parent[i] << " ";
}
}⇒ 해당 코드는 만약 하나의 그래프로 쭉~연결되어 있다면 최대 O(V)시간이 걸릴 수 있다
노드개수가 V이고 find 혹은 union연산 개수가 M개인 경우 전체 시간복잡도는 O(VM)이 되어 비효율적임
find 과정을 최적화 하는 법
- 경로 압축기법 - 재귀적 호출한 뒤 부모 테이블값 갱신
int findParent(int num) {
if (num == parent[num]) return num;
return parent[num] = findParent(parent[num]);
}서로소 집합을 활용한 사이클 판별
무방향 그래프 내에서의 사이클 판별할 때 사용
- 각 간선을 확인하며 두 노드의 루트 노드를 확인
- 루트 노드가 서로 다르면 두 노드에 대해 union연산 수행
- 루트 노드가 서로 같다면 사이클 발생
- 그래프에 포함되어 있는 모든 간선에 대해 1번 과정 반복
#include <stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <deque>
#include <stack>
#include <vector>
#include<cstdio>
#include<algorithm>
#include<memory.h>
#include<queue>
#include<map>
#define MAX 100001
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정
using namespace std;
int parent[MAX];
int V, E;
int findParent(int num) {
if (num == parent[num]) return num;
return parent[num] = findParent(parent[num]);
}
void func(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a > b) parent[a] = b;
else parent[b] = a;
}
int main(void) {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin >> V >> E;
bool check;
for (int i = 1; i <= V; i++) {
parent[i] = i;
}
for (int i = 0; i < E; i++) {
int a, b;
cin >> a >> b;
if (findParent(a) == findParent(b)) {
check = false;
}
else {
func(a, b);
}
}
if (check) {
cout << "사이클 없음";
}
else {
cout << "사이클 있음";
}
}
'Algorithm' 카테고리의 다른 글
| [프로그래머스]이중우선순위큐 - 힙 (0) | 2020.06.25 |
|---|---|
| [프로그래머스] 디스크컨트롤러 - 힙 (0) | 2020.06.24 |
| [프로그래머스-그리디] 체육복 (0) | 2020.05.11 |
