최소 신장 트리 (MST)
최소 신장 트리란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다.
특징
- 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하면 사용할 수 없다.
- N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개다.
구현 방법
1. 에지 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화
최소 신장 트리는 에지 중심으로 데이터를 저장하여 사용한다.
사이클 처리를 위한 유니온 파인드 배열도 함께 초기화 한다.
(배열의 인덱스를 해당 자리의 값으로 초기화 하면 됨)
2. 그래프 데이터를 가중치 기준으로 정렬하기
에지 리스트에 담긴 그래프 데이터를 가중치 기준으로 오름차순 정렬한다.
3. 가중치가 낮은 에지부터 연결을 시도한다
에지를 연결했을 때 사이클이 형성되지 않는 경우에만 연결 한다.
연결한 에지의 개수가 N-1개가 될 때까지 반복한다.
4. 연결된 에지의 cost를 계산한다.
연습문제
코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void BFS(int sRow, int sCol);
void GetEdges();
void SetLandNum();
int MST();
int find(int num);
void unionFunc(int a, int b);
struct node
{
bool bIsLand;
int LandNum = -1;
};
struct edge
{
int s;
int e;
int cost;
bool operator > (const edge& temp) const
{
return cost > temp.cost;
}
};
int n, m;
int LandCnt = 1;
priority_queue<edge,vector<edge>,greater<edge>> edges, start, end;
vector<vector<node>> g;
vector<vector<bool>> bIsVisted;
vector<int> unionVec;
int dRow[4] = { 1,-1,0,0 };
int dCol[4] = { 0,0,1,-1 };
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
bIsVisted = vector<vector<bool>>(n + 1, vector<bool>(m + 1));
g = vector<vector<node>>(n + 1, vector<node>(m + 1));
for (int i = 1; i <= n; i++)
{
node v;
for (int j = 1; j <= m; j++)
{
cin >> v.bIsLand;
g[i][j] = v;
}
}
SetLandNum();
GetEdges();
unionVec = vector<int>(LandCnt + 1, 0);
for (int i = 1; i < LandCnt + 1; i++)
{
unionVec[i] = i;
}
cout << MST();
}
int MST()
{
int usedEdge = 0;
int result = 0;
while (!edges.empty())
{
edge cur = edges.top();
edges.pop();
if (find(cur.s) != find(cur.e))
{
unionFunc(cur.s, cur.e);
result += cur.cost;
usedEdge++;
}
if (usedEdge == LandCnt-1)
{
return result;
}
}
return -1;
}
void unionFunc(int a, int b)
{
a = find(a);
b = find(b);
if (a != b)
{
unionVec[b] = a;
}
}
int find(int num)
{
if (unionVec[num] == num)
{
return num;
}
return unionVec[num] = find(unionVec[num]);
}
void SetLandNum()
{
//섬 번호 부여
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (bIsVisted[i][j] == 0 && g[i][j].bIsLand)
{
BFS(i, j);
}
}
}
LandCnt--;
}
void GetEdges()
{
//상하좌우 확인해서 다른 섬이면 엣지로 추가, 같은 섬이면 바로 컨티뉴
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (g[i][j].LandNum == -1)
{
continue;
}
//왼쪽 확인
int row = i;
int col = j - 1;
for (; col > 0; --col)
{
if (g[row][col].LandNum == g[i][j].LandNum)
{
break;
}
else if (g[row][col].LandNum != -1)
{
if (j - col - 1 == 1)
{
break;
}
edges.push({ g[i][j].LandNum,g[row][col].LandNum, j - col - 1 });
break;
}
}
//위쪽 확인
row = i - 1;
col = j;
for (; row > 0; --row)
{
if (g[row][col].LandNum == g[i][j].LandNum)
{
break;
}
else if (g[row][col].LandNum != -1)
{
if (i - row - 1 == 1)
{
break;
}
edges.push({ g[i][j].LandNum,g[row][col].LandNum, i - row - 1 });
break;
}
}
}
}
}
void BFS(int sRow, int sCol)
{
queue<pair<int, int>> q;
q.push({ sRow, sCol });
bIsVisted[sRow][sCol] = 1;
g[sRow][sCol].LandNum = LandCnt;
while (!q.empty())
{
pair<int, int> cur = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int nextRow = cur.first + dRow[i];
int nextCol = cur.second + dCol[i];
if (nextRow > 0 && nextRow <= n && nextCol > 0 && nextCol <= m)
{
if (bIsVisted[nextRow][nextCol] == 0 && g[nextRow][nextCol].bIsLand == 1)
{
g[nextRow][nextCol].LandNum = LandCnt;
q.push({nextRow,nextCol});
bIsVisted[nextRow][nextCol] = 1;
}
}
}
}
LandCnt++;
}회고 및 느낀점
일단 가장 큰 문제는 이거 푸는데 거의 2시간 걸렸다.
처음 아이디어를 세울 때 조금 생각을 잘못한 것 때문에 시간이 꽤 오래걸려버렸다.
처음 생각은
- BPS로 노드에 섬 번호를 매긴다
- 순회하면서 엣지를 생성한다
- 엣지로 MST를 한다
였는데 문제는 엣지를 생성하는 과정. 순회하면서 if문으로 예외 처리를 했는데 위치가 좀 이상했다. 이 때문에 엣지의 수가 더럽게 많아지는 바람에 당황했고 이것을 찾는데 시간이 좀 걸린 것 같다.
중요한 점은 이거였다.
- 엣지 생성을 위한 탐색 중에 예외를 만나면 바로 탐색을 중지한다.
섬을 뚫고 다른 섬에 도착하거나 거리가 1이어서 안되는데 거리가 2인 노드에 엣지가 형성되어 버려 이상한 값들이 나왔다.
만약 if로 예외를 처리해야한다면 위치와 해당 if의 처리를 확실히 해야겠다..
영차 영차