11. 최단거리 (충남대 알고리즘 강의록)

충남대학교 컴퓨터공학과 이영석 교수님의 "알고리즘" 강의 실습 내용입니다.

• 실습 문제들의 코드 위주로 구성되어 있습니다.

문제 1: Dijkstra Algorithm 구현 §

#include <functional>
#include <iostream>
#include <vector>
#include <array>
#include <queue>
#include <map>
 
using namespace std;
 
#define TOOFAST ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#define INTMAX 2147483647
#define COST 0
#define NODE 1
 
struct Info {
	string node;
	int cost;
	Info(): node(""), cost(INTMAX) {}
	Info(string n, int c): node(n), cost(c) {}
	bool operator<(Info t) const { return this->cost < t.cost; }
	bool operator>(Info t) const { return this->cost > t.cost; }
	bool operator==(Info t) const { return this->cost == t.cost; }
};
 
int main() {
	TOOFAST;
 
	int V, E;
	cin >> V >> E;
 
	string start, end;
	cin >> start >> end;
 
	// 각 노드에 대해 바로 이전에 방문한 노드와 해당 노드에 도달하기까지의 최소비용을 저장하기 위함
	map<string, Info> D;
	// 각 노드와 연결된 노드 및 비용을 저장하기 위함
	map<string, vector<Info>> conn;
	// 방문한 노드를 체크하기 위함
	map<string, bool> selected;
	// 존재하는 노드를 입력받으며 각 자료구조를 초기화함
	for(int i = 0; i < V; i++) {
		string v;
		cin >> v;
		D[v] = Info(start, INTMAX);
		conn[v] = {};
		selected[v] = false;
	}
 
	// 양방향 연결관계를 생성해줌
	for(int i = 0; i < E; i++) {
		string u, v;
		int w;
		cin >> u >> v >> w;
		conn[u].push_back(Info(v, w));
		conn[v].push_back(Info(u, w));
	}
 
	// 시작노드의 비용을 0으로 바꿔줌
	D[start].cost = 0;
 
	// 주어진 시작노드에서 출발하도록 함
	priority_queue<Info, vector<Info>, greater<Info>> pq;
	pq.push(Info(start, 0));
 
	while(!pq.empty()) {
 
		// 현재 이동비용이 제일 적은 경로를 선택
		auto h = pq.top();
		pq.pop();
 
		// 선택된 노드를 방문함으로 변경
		selected[h.node] = true;
 
		for(const auto& next : conn[h.node]) {
 
			// 현재 노드와 연결된 노드중 이미 방문한 노드는 무시함
			if(selected[next.node]) {
				continue;
			}
 
			// 시작지점에서 현재 노드와 연결된 노드까지 가는 비용이 현재 노드를 거쳐서 가는 비용보다 클 경우
			// 해당 노드의 최소비용을 현재 노드를 거칠때의 비용으로 수정하고
			// 바로 이전에 방문한 노드를 현재 노드로 지정해주며
			// 우선순위 큐에 넣어줌
			if(D[next.node].cost > D[h.node].cost + next.cost) {
				D[next.node].cost = D[h.node].cost + next.cost;
				D[next.node].node = h.node;
				pq.push(Info(next.node, D[next.node].cost));
			}
		}
	}
 
	// 종점노드까지의 이동경로를 알아내기 위해 바로 이전에 방문한 노드를 추적함
	vector<string> path = { end };
	string it = end;
	while(it != start) {
		path.push_back(D[it].node);
		it = D[it].node;
	}
 
	// 결과 출력
	for(auto rit = path.rbegin(); rit < path.rend(); rit++) {
		cout << *rit;
	}
	cout << '\n';
	cout << D[end].cost << '\n';
 
	return 0;
}

문제 2: Bellman-Ford Algorithm 구현 §

#include <iostream>
#include <vector>
#include <array>
#include <map>
 
using namespace std;
 
#define TOOFAST ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#define INTMAX 2147483647
 
struct Edge {
	string first, second;
	int cost;
};
 
int main() {
	TOOFAST;
 
	int V, E;
	cin >> V >> E;
 
	string start, end;
	cin >> start >> end;
 
	// 바로 이전에 거쳤던 간선과 해당 노드에 가기까지의 최소비용을 저장하기 위함
	map<string, pair<Edge, int>> D;
	// 노드 정보를 입력받으며 자료구조를 초기화함
	for(int i = 0; i < V; i++) {
		string v;
		cin >> v;
		D[v] = make_pair(Edge{start, start, INTMAX}, INTMAX);
	}
	D[start].second = 0;
 
	// 단방향 간선의 정보를 입력받음
	vector<Edge> edges;
	edges.reserve(2 * E);
	for(int i = 0; i < E; i++) {
		string first, second;
		int cost;
		cin >> first >> second >> cost;
		edges.push_back(Edge{first, second, cost});
	}
 
	// 모든 노드에 대해
	for(int i = 0; i < V - 1; i++) {
		// 모든 간선을 조사하며
		for(const auto& edge : edges) {
			// 간선의 시작점까지의 최소비용이 무한대가 아니고 간선의 도착점까지의 최소비용이
			// 간선의 시작점까지의 최소비용과 간선의 비용을 합한 것보다 클때
			// 합한 값으로 최소비용을 수정함
			if(D[edge.first].second != INTMAX && D[edge.second].second > D[edge.first].second + edge.cost) {
				D[edge.second].second = D[edge.first].second + edge.cost;
				D[edge.second].first = edge;
			}
		}
	}
 
	// 모든 간선에 대해 한번 더 동일한 과정을 거쳤을때 변화가 생긴다면 최소비용이 음의 무한대인 경로가 존재하므로
	// 최소비용을 알 수 없음을 출력함
	for(const auto& edge : edges) {
		if(D[edge.first].second != INTMAX && D[edge.second].second > D[edge.first].second + edge.cost) {
			cout << "Negative\n";
			return 0;
		}
	}
 
	// 바로 이전에 방문한 노드를 추적하며 목적지까지 가는 최소비용 경로를 알아냄
	vector<Edge> path = { D[end].first };
	string it = end;
	while(it != start) {
		path.push_back(D[it].first);
		it = D[it].first.first;
	}
 
	// 결과를 출력함
	for(auto rit = path.rbegin(); rit < path.rend() - 1; rit++) {
		cout << rit->first << ' ' << rit->second << ' ' << (rit->cost) << '\n';
	}
 
	return 0;
}

문제 3: 호캉스 §

#include <iostream>
#include <map>
#include <vector>
 
using namespace std;
 
#define TOOFAST ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#define INTMAX 2147483647
 
struct Edge{
	string src, dst;
	int cost;
};
 
int main() {
	TOOFAST;
 
	int V, E, L;
	cin >> V >> E >> L;
 
	vector<string> nodes(V);
	for(int i = 0; i < V; i++) {
		cin >> nodes[i];
	}
 
	// 한 노드에서 다른 노드로 가는 비용을 초기화함
	map<string, map<string, int>> D;
	for(const auto& s : nodes) {
		for(const auto& d : nodes) {
			if(s == d) {
				D[s][d] = 0;
			} else {
				D[s][d] = INTMAX;
			}
		}
	}
 
	// 간선의 정보를 입력받아 양방향 연결관계를 맺어줌
	for(int i = 0; i < E; i++) {
		string src, dst;
		int cost;
		cin >> src >> dst >> cost;
		D[src][dst] = cost;
		D[dst][src] = cost;
	}
 
	for(const auto& k : nodes) {
		for(const auto& i : nodes) {
			for(const auto& j : nodes) {
				// 노드 i에서 j로 가는 비용이 노드 k를 거쳐 가는 것이 더 비용이 적다면 최소비용을 수정함
				if((D[i][k] != INTMAX) && (D[k][j] != INTMAX)) {
					D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
				}
			}
		}
	}
 
	string resNode = "";
	int resNum = -1;
	for(const auto& v : nodes) {
		int cnt = 0;
		// 각 노드에 대해 연결된 노드들과의 비용이 주어진 한계보다 작은 노드들의 갯수를 셈
		for(const auto& n : nodes) {
			if(D[v][n] <= L) {
				cnt++;
			}
		}
		// 노드 갯수의 최대값을 수정함
		if(cnt > resNum) {
			resNum = cnt;
			resNode = v;
		}
	}
 
	// 출력
	cout << resNode << ' ' << resNum << '\n';
 
	return 0;
}