충남대학교 컴퓨터공학과 이영석 교수님의 "알고리즘" 강의 실습 내용입니다.
- 실습 문제들의 코드 위주로 구성되어 있습니다.
문제 1: MST 구현
#include <iostream>
#include <vector>
#include <array>
#include <map>
#include <queue>
using namespace std;
#define toofast ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
// 어떤 노드와 연결된 노드와 비용을 저장
struct Node {
string next;
int cost;
Node(string n, int c) { next = n; cost = c; }
bool operator<(Node n) const { return this->cost < n.cost; }
bool operator>(Node n) const { return this->cost > n.cost; }
bool operator==(Node n) const { return this->cost == n.cost; }
};
int main() {
toofast;
int V, E;
cin >> V >> E;
// 노드들을 입력받음
string vv;
map<string, vector<Node>> conn;
map<string, bool> visited;
for(int i = 0; i < V; i++) {
cin >> vv;
conn[vv] = {};
visited[vv] = false;
}
// 간선에 대한 정보를 입력받아 양방향 연결관계를 지어줌
for(int i = 0; i < E; i++) {
string u, v;
int c;
cin >> u >> v >> c;
conn[u].push_back(Node(v, c));
conn[v].push_back(Node(u, c));
}
priority_queue<Node, vector<Node>, greater<Node>> pq;
// 임의의 노드에서부터 시작
pq.push(Node(vv, 0));
int res = 0;
while(true) {
// 방문하지 않은 노드 중 비용이 최소인 노드를 얻음
Node h = pq.top();
do {
h = pq.top();
pq.pop();
} while (visited[h.next] && !pq.empty());
if(!visited[h.next]) {
// 방문하지 않은 비용이 최소인 노드의 비용을 저장하고
// 해당 노드와 연결되어있는 노드들을 우선순위 큐에 넣어줌
visited[h.next] = true;
res += h.cost;
for(const auto& connEdge : conn[h.next]) {
pq.push(connEdge);
}
} else {
break;
}
}
cout << res << '\n';
return 0;
}문제 2: 두번째 최소 비용
#include <iostream>
#include <vector>
#include <array>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
#define toofast ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
// 간선의 정보를 저장하기 위한 자료구조
struct Edge {
string first;
string second;
int cost;
Edge(string f, string s, int c) { first = f; second = s; cost = c; }
bool operator<(Edge e) const { return this->cost < e.cost; }
bool operator>(Edge e) const { return this->cost > e.cost; }
bool operator==(Edge e) const { return this->cost == e.cost; }
};
class RankSet {
map<string, string> parent;
map<string, int> rank;
public:
// 노드 리스트를 받아 Union set을 초기화함
// 부모를 자기 자신으로 해 자신을 루트로 설정하고
// 자신의 높이를 0으로 설정함
RankSet(const vector<string>& nodes) {
for(const auto& node : nodes) {
parent[node] = node;
rank[node] = 0;
}
}
// 부모가 자기자신이면 루트이므로 반환하고
// 자기 자신이 아니라면 부모에 대해 재귀적으로 호출함
string findRoot(const string& target) {
if(parent[target] == target) { return target; }
return findRoot(parent[target]);
}
// 입력받은 두 노드의 루트를 구한 후
// 루트를 하나로 합쳐 합집합을 수행함
void unionSet(const string& u, const string& v) {
string uRoot = findRoot(u), vRoot = findRoot(v);
if(rank[uRoot] < rank[vRoot]) {
parent[uRoot] = vRoot;
} else {
parent[vRoot] = uRoot;
if(rank[uRoot] == rank[vRoot]) {
rank[uRoot]++;
}
}
}
};
int main() {
toofast;
int V, E;
cin >> V >> E;
// 노드에 대한 정보 입력
vector<string> nodes(V);
for(int i = 0; i < V; i++) {
cin >> nodes[i];
}
// 간선들에 대한 정보 입력
vector<Edge> edges;
edges.reserve(E);
for(int i = 0; i < E; i++) {
string u, v;
int c;
cin >> u >> v >> c;
edges.push_back(Edge(u, v, c));
}
// 간선들을 비용에 따라 오름차순으로 정렬
sort(edges.begin(), edges.end());
set<int> costs;
// 비활성화시킬 간선을 하나 지정해 이외의 간선들로 최소비용을 구함
for(int i = 0; i < E; i++) {
RankSet rs(nodes);
int res = 0;
for(int j = 0; j < E; j++) {
if(i != j) {
auto edge = edges[j];
if(rs.findRoot(edge.first) != rs.findRoot(edge.second)) {
res += edge.cost;
rs.unionSet(edge.first, edge.second);
}
}
}
// 구한 최소비용을 set에 넣어 중복을 제거하고 오름차순으로 정렬
costs.insert(res);
}
// 구한 최소비용들 중 두번째로 적은 값을 출력함
auto it = costs.begin();
it++;
cout << *it << endl;
return 0;
}문제 3: 통신망 구축
#include <iostream>
#include <vector>
#include <array>
#include <map>
#include <queue>
using namespace std;
#define toofast ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
int main() {
toofast;
int V, E;
cin >> V >> E;
// 건설비용들을 입력받고 최소비용을 갖는 노드를 저장
vector<int> buildCosts(V + 1, 2147483647);
int minBuildCost = 0;
for(int i = 1; i <= V; i++) {
cin >> buildCosts[i];
if(buildCosts[i] < buildCosts[minBuildCost]) {
minBuildCost = i;
}
}
// 간선들을 입력받아 양방향 연결관계를 연결비용과 함께 저장
map<int, vector<array<int, 2>>> conn;
for(int i = 0; i < E; i++) {
int u, v, c;
cin >> u >> v >> c;
if(conn.count(v) == 0) { conn[v] = {}; }
conn[u].push_back({c, v});
if(conn.count(u) == 0) { conn[u] = {}; }
conn[v].push_back({c, u});
}
priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;
// 우선순위큐에 최소건설비용을 갖는 노드를 넣어 해당 노드에서부터 시작하도록 함
pq.push({buildCosts[minBuildCost], minBuildCost});
vector<bool> visited(V + 1, false);
int res = 0;
while(true) {
// 최소 건설 혹은 연결 비용을 갖는 노드를 선택함
array<int, 2> h;
do {
h = pq.top();
pq.pop();
} while (visited[h[1]] && !pq.empty());
if(!visited[h[1]]) {
visited[h[1]] = true;
// 해당 노드의 건설 혹은 연결 비용을 결과값에 더함
res += h[0];
// 해당 노드와 연결할 수 있는 간선들을 우선순위 큐에 추가함
for(const auto& connEdge : conn[h[1]]) {
pq.push(connEdge);
}
// 방문하지 않은 모든 노드의 건설비용을 우선순위큐에 추가함
for(int i = 1; i <= V; i++) {
if(!visited[i]) {
pq.push({buildCosts[i], i});
}
}
} else {
break;
}
}
cout << res << '\n';
return 0;
}