12. A-star, 위상정렬 (충남대 알고리즘 강의록)

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

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

문제 1: 얼음장수 §

#include <cstdlib>
#include <iostream>
#include <vector>
#include <array>
#include <cmath>
#include <queue>
 
using namespace std;
 
#define ROW 0
#define COL 1
#define BEG -1
#define END -2
 
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, 1, 0, -1 };
array<int, 2> start, endd;
 
// 좌표의 정보를 담는 구조체
struct Cor {
	int row, col, G, H;
 
	// 좌표 객체를 생성하면 Heuristic값이 자동으로 계산됨
	Cor(const int& r, const int& c, const int& g): row(r), col(c), G(g) {
		int dr = r - endd[ROW];
		int dc = c - endd[COL];
		H = sqrt(dr*dr + dc*dc);
	}
 
	// 좌표의 대소비교는 G와 Heuristic를 더한 값을 기준으로 수행됨
	bool operator<(const Cor& c) const { return this->G + this->H < c.G + c.H; }
	bool operator>(const Cor& c) const { return this->G + this->H > c.G + c.H; }
	bool operator==(const Cor& c) const { return this->G + this->H == c.G + c.H; }
};
 
int main() {
	int R, C, ice;
	cin >> R >> C >> ice;
 
	// 입력값으로 좌표평면을 초기화하고 방문체크용 배열도 초기화함
	vector<vector<int>> matrix(R, vector<int>(C));
	vector<vector<bool>> visited(R, vector<bool>(C, false));
	for(int r = 0; r < R; r++) {
		string line;
		cin >> line;
		for(int c = 0; c < C; c++) {
			switch(line[c]) {
				case 'S' : matrix[r][c] = BEG; start[ROW] = r; start[COL] = c; visited[r][c] = true; break;
				case 'E' : matrix[r][c] = END; endd[ROW] = r; endd[COL] = c; break;
				default: matrix[r][c] = line[c] - '0';
			}
		}
	}
 
	// 우선순위 큐를 생성하여 G + Heuristic값이 작은 좌표를 선택하도록 함
	priority_queue<Cor, vector<Cor>, greater<Cor>> pq;
	// 시작지점을 우선순위 큐에 넣어줌
	pq.push(Cor(start[ROW], start[COL], 0));
	while(!pq.empty()) {
		auto h = pq.top();
		pq.pop();
 
		// 현재 좌표가 종료지점이면 녹은 얼음의 양을 초기 얼음의 양에서 빼준 뒤 반복문을 빠져나옴
		if(matrix[h.row][h.col] == END) {
			ice -= h.G - END;
			break;
		}
 
		for(int d = 0; d < 4; d++) {
			int nr = h.row + dr[d];
			int nc = h.col + dc[d];
			if(0 <= nr && nr < R && 0 <= nc && nc < C) {
				// 현재좌표와 인접한 좌표가 방문하지 않은 좌표라면 우선순위 큐에 넣어주고 방문체크함
				if(!visited[nr][nc]) {
					// G의 값으로 지금까지 녹은 얼음의 양과 해당 좌표로 갈 경우 녹는 얼음의 양의 합을 설정함
					pq.push(Cor(nr, nc, h.G + matrix[nr][nc]));
					visited[nr][nc] = true;
				}
			}
		}
	}
 
	// 결과 출력
	if(ice < 0) {
		cout << "FAIL" << endl;
	} else {
		cout << ice << endl;
	}
 
	return 0;
}

문제 2: 위상정렬 §

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
 
using namespace std;
 
#define umap unordered_map
#define uset unordered_set
 
int main() {
	int N, E;
	cin >> N >> E;
 
	// 한 노드에서 갈 수 있는 다음 노드들을 저장
	umap<string, vector<string>> nextIs;
	// 해당 노드를 방문하기 위해 먼저 방문해야 되는 노드들을 저장
	umap<string, vector<string>> beforeIs;
	// 선행노드가 없는 노드가 시작지점이기 때문에 그러한 노드를 저장하기 위한 set
	uset<string> noDepend;
	// 각 자료구조들을 초기화함
	for(int i = 0; i < N; i++) {
		string node;
		cin >> node;
		nextIs[node] = {};
		beforeIs[node] = {};
		noDepend.insert(node);
	}
 
	// 후행노드, 선행노드 연결관계를 입력받고
	// 선행노드가 있는 노드를 시작지점 집합에서 삭제함
	for(int i = 0; i < E; i++) {
		string s, d;
		cin >> s >> d;
		nextIs[s].push_back(d);
		beforeIs[d].push_back(s);
		noDepend.erase(d);
	}
 
	// 방문한 노드를 체크하기 위함
	uset<string> completed;
	// 정렬된 결과를 담음
	vector<string> seq;
	seq.reserve(N);
	// 큐를 생성하고 시작지점 집합에 들어있는 노드들을 넣어줌
	queue<string> q;
	for(auto it = noDepend.begin(); it != noDepend.end(); it++) {
		q.push(*it);
	}
	while(!q.empty()) {
		auto cur = q.front();
		q.pop();
 
		// 큐의 head를 방문처리해주고 정렬결과에 담음
		completed.insert(cur);
		seq.push_back(cur);
 
		// 현재 노드의 모든 후행노드에 대해서
		for(const auto& next : nextIs[cur]) {
			// 해당 후행 노드의 선행 노드가 모두 완료되었는지 체크
			bool dependCompl = true;
			for(const auto& depend : beforeIs[next]) {
				if(completed.count(depend) == 0) {
					dependCompl = false;
				}
			}
			// 선행노드가 모두 완료되었다면 큐에 넣어줌
			if(dependCompl) {
				q.push(next);
			}
		}
	}
 
	// 결과 출력
	for(int i = 0; i < N - 1; i++) {
		cout << seq[i] << ' ';
	}
	cout << seq.back() << endl;
}

문제 3: 네비게이션 §

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
#define MAXINT 2147483647
 
int main() {
	int N;
	cin >> N;
 
	// 간선의 용량을 저장
	vector<vector<int>> capp(N, vector<int>(N, 0));
	// 간선에 흐르는 유량을 저장
	vector<vector<int>> flow(N, vector<int>(N, 0));
	// 노드 연결 관계 저장
	vector<vector<int>> conn(N);
 
	// 자료구조 초기화
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			int c;
			cin >> c;
			if(c > 0) {
				capp[i][j] += c;
				conn[i].push_back(j);
				conn[j].push_back(i);
			}
		}
	}
 
	int tot = 0;
	const int beg = 0, endd = N - 1;
	while(true) {
		// 시작지점에서 종료지점까지의 경로를 하나 선택함
 
		// 어떤 노드를 방문하기 바로 직전에 방문했던 노드를 저장하는 방식으로 경로를 저장함
		vector<int> prev(N, -1);
 
		// 시작지점부터 BFS로 탐색
		queue<int> q;
		q.push(beg);
		// prev[endd] == -1이라면 아직 목적지까지 도달한것이 아니므로
		while(!q.empty() && prev[endd] == -1) {
			auto curr = q.front();
			q.pop();
			for(auto& next : conn[curr]) {
				// 현재 노드와 연결된 다음 노드가 방문한 적이 없어야 하고
				if(prev[next] == -1) {
					// 현재 노드에서 다음 노드로 가는 간선의 용량이 유량보다 많아야 됨
					if(capp[curr][next] > flow[curr][next]) {
						prev[next] = curr;
						// 다음 노드가 목적지일 경우 break를 걸어 제일 먼저 찾은 경로를 검토하게 함
						if(next == endd) { break; }
						q.push(next);
					}
				}
			}
		}
 
		// 경로상의 모든 간선에 대해 유량이 용량보다 작은 경로를 찾지 못한 경우
		if(prev[endd] == -1) { break; }
 
		// 찾은 경로에서 추가적으로 흘려보낼 수 있는 유량의 양을 계산함
		int nextFlow = MAXINT;
		for(auto it = endd; it != beg; it = prev[it]) {
			// 경로상의 (용량 - 유량)의 최솟값을 구하면 그것이 모든 간선을 통과할 수 있는 유량이 됨
			nextFlow = min(nextFlow, capp[prev[it]][it] - flow[prev[it]][it]);
		}
 
		// 경로상의 모든 간선에 유량을 추가함
		for(auto it = endd; it != beg; it = prev[it]) {
			flow[prev[it]][it] += nextFlow;
			// 한방향으로 유체가 흐른다는 것은 반대방향으로 음의 유량이 흐른다고도 해석할 수 있으므로
			// 경로의 간선에 대해 반대방향으로 음의 유량을 더해줌
			flow[it][prev[it]] -= nextFlow;
		}
 
		// 총 흐르고 있는 유량의 크기를 더해줌
		tot += nextFlow;
	}
 
	// 결과 출력
	cout << tot << endl;
	return 0;
}