최소 스패닝 트리 - 그래프/트리의 응용
최소 스패닝 트리를 알아보기 위한 자료구조가 있다.
상호 배타적 집합(Disjoint Set) -> 유니온-파인드 라고도 함.(합치기-찾기)
상호 배타적 집합 코드
예로 알아본다. 리니지 배틀그라운드 라는 혼종을 만든다!
혈맹전 + 서바이벌을 합치는 게임을 만든다면?
1인 팀 1000명 (팀id 0 ~ 999 ) 고유 id 부여 동맹 시스템 있음 ( 1번팀 + 2번팀 = 하나의 팀 ) 이렇게 됨
일반적으로 팀 병합을 한다면 시간복잡도 O(n) 으로 안좋음
void NewGame()
{
struct User
{
// 내가 속해 있는 팀을 Id 로 구분
int teamId;
// TODO
};
// TODO : UserManager
vector<User> users;
for (int i = 0; i < 1000; i++)
{
users.push_back(User{ i });
}
// 팀 동맹 ( 유니온 ) 요런 느낌의 합치기 비스무리
users[5].teamId = users[1].teamId; // 1로 병합
// 문제는 합칠게 엄청 많다면?
// [1][1][1][1][1][1]....[2][2][2][2][2][2]
// 1번 팀 소속을 전부 2번 팀 소속으로 변경시
for (User& u : users)
{
if (u.teamId == 1)
u.teamId = 2;
}
// 찾기 연산 (몇 번째 유저의 팀은 몇 번인가요?) O(1) 인덱스로 빠르게 접근 가능하다.
// 합치기 연산 O(N) 느림....
// 이 합치기 연산을 더 빠르고 효율적으로 사용하기 위해 만든어진 자료구조가 상호 배타적 집합
}
유니온 파인드 코드
class DisjointSet
{
public:
class DisjointSet(int n) : _parent(n), _rank(n,1)
{
for (int i = 0; i < n; i++)
{
_parent[i] = i;
}
}
// 너 리더 누구임?
int Find(int u)
{
if (u == _parent[u])
return u;
// 이렇게 해서 u 가 리더의 바로 아래 계층에 오도록 만든다.
_parent[u] = Find(_parent[u]);
return _parent[u];
}
// u와 v를 합친다. (rank 비교 후 합병)
void Merge(int u, int v)
{
u = Find(u);
v = Find(v);
// 같은 팀 소속이면 합병 안해도 됨!
if (u == v)
return;
// u 가 v 보다 rank 가 낮거나 같음을 보장하게 만들기
if (_rank[u] > _rank[v])
swap(u, v);
_parent[u] = v;
// 만약 랭크(높이)가 같으면 u의 계층이 v의 바로 아래 계층에 들어오면서 v 계층이 1증가되야함
// [1] [3]
// [2] [4][5][1]
// [2] << 이렇게 들어오면서 계층이 +1된다
if (_rank[u] == _rank[v])
_rank[v]++;
}
private:
vector<int> _rank;
vector<int> _parent;
};
최소 신장 트리는 그리드를 이용.
그래프인데 간선의 수를 최소화해서 모든 노드들을 연결하는 트리
이 말은 사이클이 생기면 안된다는 뜻이다. 삼각형이든 사각형이든 사이클 안생겨야함. 결과적으로 정점이 N개이면 간선은 N - 1 개가 최소한의 간선 수라는 것을 알 수 있다.
최소 스패닝 트리 (MST) 를 만드는데 대표적인 알고리즘 KRUSKAL 크루스칼 알고리즘 그리디 사용.
순간에 최적인 답을 선택 후 결과 도출.
그리디 사용하다가 MST 의 규칙을 위배할 경우 수정 알고리즘까지 포함하는 알고리즘이 KRUSKAL 알고리즘
일단 그래프를 만들고
struct Vertex
{
// TODO
};
vector<Vertex> vertices;
vector<vector<int>> adjacent;
void CreateGraph()
{
vertices.resize(6);
adjacent = vector<vector<int>>(6, vector<int>(6, -1));
adjacent[0][1] = adjacent[1][0] = 15;
adjacent[0][3] = adjacent[3][0] = 35;
adjacent[1][2] = adjacent[2][1] = 5;
adjacent[1][3] = adjacent[3][1] = 10;
adjacent[3][4] = adjacent[4][3] = 5;
adjacent[3][5] = adjacent[5][3] = 10;
adjacent[5][4] = adjacent[4][5] = 5;
}
크루스칼 알고리즘을 이용한 최소 신장 트리
struct CostEdge
{
int cost;
int u;
int v;
bool operator<(CostEdge& other)
{
return cost < other.cost;
}
};
// 최소 간선 수의 최종 비용 반환
int Kruskal(vector< CostEdge>& selected)
{
int ret = 0;
selected.clear();
vector<CostEdge> edges;
for (int i = 0; i < adjacent.size(); ++i)
{
for (int j = 0; i < adjacent[i].size(); ++j)
{
// 양방향 이라서 2번 추가되는거 방지
if (i > j)
continue;
if (adjacent[i][j] != -1)
{
edges.push_back(CostEdge{ adjacent[i][j], i, j });
}
}
}
sort(edges.begin(), edges.end());
DisjointSet sets(vertices.size());
for (CostEdge& edge : edges)
{
// 같은 그룹이면 스킵 사이클 생성 예방
if (sets.Find(edge.u) == sets.Find(edge.v))
{
continue;
}
// 두 그룹 합병
sets.Merge(edge.u, edge.v);
selected.push_back(edge);
ret += edge.cost;
}
return ret;
}
결과 확인
위에서 만든 그래프를 최소 비용으로 연결한다면 0-1-3-4-5 로 연결되고 1-2 를 연결하면 된다. 당연히 이 최소 비용으로 연결된 그래프의 간선 수는 5이다. 전체 노드가 6개니까
반환 값 ret 이 전체 간선 최소 비용을 알려준다.