BOJ 백준 17472 : 다리 만들기 2
Updated:
시작하면서
이번 문제는 최소 스패닝 트리(MST: Minimum Spanning Tree) 를 사용해 구현하는 문제이다.
문제 이해
이 문제는 최소 스패닝 트리를 사용해서 구현하는 문제이다. 우선 이 문제를 최소 스패닝 트리 문제로 만들기 위해서는 다음과 같이 생각해야 한다.
- 각 섬들은 하나의 노드이다.
- 각 섬들을 연결하는 다리는 간선이다.
이렇게 만든 후에는 최소 스패닝 트리를 해결하는 알고리즘을 사용해서 문제를 해결하면 된다. 최소 스패닝 트리는 일반적으로 크루스칼 알고리즘 혹은 프림 알고리즘을 사용해서 해결한다.
크루스칼 알고리즘의 시간 복잡도는 O(ElogE), 프림 알고리즘의 시간 복잡도는 O(ElogV)이다. 이 문제에서는 간선과 정점의 개수가 그렇게 많지 않으니 어떤 알고리즘을 선택하든 상관없을 것으로 보인다. 좀 더 풀기 쉬운 크루스칼 알고리즘으로 문제를 해결했다.
문제 해결 방법은 다음과 같다.
- 인풋으로 받은 map의 섬들을 인덱싱한다.
- 각 섬들끼리 이어서 간선을 만든다.
- 해당 간선들을 길이에 따라 오름차순으로 정렬한다.
- 이때 중복된 간선들이 있는데, 간선의 개수가 많지 않기 때문에 굳이 제거하지는 않았다.
- 각 섬들에 자기 자신을 부모로 만든다.
- 크루스칼 알고리즘을 사용해서 최소 길이의 간선들로 섬들을 연결한다.
- 이때 연결된 섬들을 같은 부모로 이어두어서 중복을 방지한다.
- 모든 섬이 연결되어 있는지 확인한다.
- 모든 섬이 연결되어 있지 않으면 답을 -1로 변경한다.
해결
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
class EdgeInfo
{
public:
int weight;
int start, end;
static int _compare(const EdgeInfo& e1, const EdgeInfo& e2)
{
return e1.weight < e2.weight;
}
};
void MakeParent(vector<int> &islandParent, int parent, int index)
{
int previousParent = islandParent[index];
for (int i = 0; i < islandParent.size(); i++)
{
if (islandParent[i] == previousParent)
{
islandParent[i] = parent;
}
}
}
int FindParent(const vector<int> &islandParent, int index)
{
if (islandParent[index] != index)
{
return FindParent(islandParent, islandParent[index]);
}
return index;
}
void MakeIsland(vector<vector<int >>& map, int index01, int index02, const int kIslandIndex)
{
if (map[index01][index02] != 1)
{
return;
}
map[index01][index02] = kIslandIndex;
// 1. 상
if (index01 - 1 >= 0)
{
MakeIsland(map, index01 - 1, index02, kIslandIndex);
}
// 2. 하
if (index01 + 1 < map.size())
{
MakeIsland(map, index01 + 1, index02, kIslandIndex);
}
// 3. 좌
if (index02 - 1 >= 0)
{
MakeIsland(map, index01, index02 - 1, kIslandIndex);
}
// 4. 우
if (index02 + 1 < map[index01].size())
{
MakeIsland(map, index01, index02 + 1, kIslandIndex);
}
}
void MakeEdgeInfos(const vector<vector<int >> &map, vector<EdgeInfo> &edgeInfos, int index01, int index02)
{
int startIslandIndex = map[index01][index02];
// 1. 상
if (index01 - 2 > 0 && map[index01 - 1][index02] == 0 && map[index01 - 2][index02] == 0)
{
for (int i = index01 - 2; i > 0; i--)
{
if (map[i][index02] == 0)
continue;
EdgeInfo edgeInfo = { 0, };
edgeInfo.start = startIslandIndex;
edgeInfo.end = map[i][index02];
edgeInfo.weight = index01 - i - 1;
edgeInfos.push_back(edgeInfo);
break;
}
}
// 2. 하
if (index01 + 2 < map.size() && map[index01 + 1][index02] == 0 && map[index01 + 2][index02] == 0)
{
for (int i = index01 + 2; i < map.size(); i++)
{
if (map[i][index02] == 0)
continue;
EdgeInfo edgeInfo = { 0, };
edgeInfo.start = startIslandIndex;
edgeInfo.end = map[i][index02];
edgeInfo.weight = i - index01 - 1;
edgeInfos.push_back(edgeInfo);
break;
}
}
// 3. 좌
if (index02 - 2 > 0 && map[index01][index02 - 1] == 0 && map[index01][index02 - 2] == 0)
{
for (int j = index02 - 2; j > 0; j--)
{
if (map[index01][j] == 0)
continue;
EdgeInfo edgeInfo = { 0, };
edgeInfo.start = startIslandIndex;
edgeInfo.end = map[index01][j];
edgeInfo.weight = index02 - j - 1;
edgeInfos.push_back(edgeInfo);
break;
}
}
// 4. 우
if (index02 + 2 < map[index01].size() && map[index01][index02 + 1] == 0 && map[index01][index02 + 2] == 0)
{
for (int j = index02 + 2; j < map[index01].size(); j++)
{
if (map[index01][j] == 0)
continue;
EdgeInfo edgeInfo = { 0, };
edgeInfo.start = startIslandIndex;
edgeInfo.end = map[index01][j];
edgeInfo.weight = j - index02 - 1;
edgeInfos.push_back(edgeInfo);
break;
}
}
}
int main()
{
// sync off
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// sync off
vector<vector<int >> map;
vector<EdgeInfo> edgeInfos;
int N, M;
cin >> N >> M;
map.resize(N);
for (int i = 0; i < N; i++)
{
map[i].resize(M);
for (int j = 0; j < M; j++)
{
cin >> map[i][j];
}
}
// 1. 인접한 섬 인덱싱
const int kStartIslandIndex = 2;
int islandIndex = kStartIslandIndex;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (map[i][j] != 1)
continue;
MakeIsland(map, i, j, islandIndex);
islandIndex++;
}
}
// 2. 섬들끼리 간선 만들기
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (map[i][j] == 0)
continue;
MakeEdgeInfos(map, edgeInfos, i, j);
}
}
// 3. 간선 정렬
sort(edgeInfos.begin(), edgeInfos.end(), EdgeInfo::_compare);
// 4. 각 섬의 부모 만들기
vector<int> islandParent(islandIndex);
for (int i = 0; i < islandParent.size(); i++)
{
islandParent[i] = i;
}
// 5. 크루스칼 알고리즘으로 문제 해결
int result = 0;
for (int i = 0; i < edgeInfos.size(); i++)
{
if (islandParent[edgeInfos[i].start] == islandParent[edgeInfos[i].end])
continue;
int parent01 = FindParent(islandParent, islandParent[edgeInfos[i].start]);
int parent02 = FindParent(islandParent, islandParent[edgeInfos[i].end]);
int parent = max(parent01, parent02);
MakeParent(islandParent, parent, islandParent[edgeInfos[i].start]);
MakeParent(islandParent, parent, islandParent[edgeInfos[i].end]);
result += edgeInfos[i].weight;
}
// 6. 모든 섬이 연결되어 있는지 확인
int anyParent = islandParent[2];
for (int i = kStartIslandIndex; i < islandParent.size(); i++)
{
if (islandParent[i] != anyParent)
{
result = -1;
}
}
cout << result;
return 0;
}
Leave a comment