8. 그래프 (충남대 알고리즘 강의록)

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

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

문제 1: 기차 여행 §

#include <iostream>
#include <map>
#include <set>
#include <queue>
 
using namespace std;
 
int main() {
	// 표준입출력
	int n, m;
	cin >> n >> m;
 
	map<string, set<string>> conn;
	map<string, bool> visited;
 
	string city;
	for(int i = 0; i < n; i++) {
		cin >> city;
		set<string> conned;
		conn[city] = conned;
		visited[city] = false;
	}
 
	// 경로 입력과 동시에 도시들 간 연결관계 선언
	for(int i = 0; i < m; i++) {
		string a, b;
		cin >> a >> b;
		// 경로 양쪽의 도시에 모두 연결되었음을 명시
		conn[a].insert(b);
		conn[b].insert(a);
	}
 
	// 너비 우선 탐색으로 연결된 모든 도시에 방문
	queue<string> q;
	// 모든 도시가 연결되었다는 가정 하에 어떤 도시에서 출발하여도
	//	 다른 모든 도시에 도달할 수 있어야 하므로 마지막으로 입력받은 도시에서 출발
	q.push(city);
	visited[city] = true;
	while(!q.empty()) {
		// 큐의 head에 있는 도시를 꺼낸 후
		auto h = q.front();
		q.pop();
		for(const auto& next : conn[h]) {
			if(!visited[next]) {
				// 연결되어있는 도시 중 방문하지 않은 도시를 방문
				visited[next] = true;
				q.push(next);
			}
		}
	}
 
	// 방문 상태를 보며 방문하지 않은 도시가 있을때 False를 출력하고 종료
	for(auto it = visited.begin(); it != visited.end(); it++) {
		if(!it->second) {
			cout << "False" << endl;
			return 0;
		}
	}
	// 모든 도시에 방문하였으면 True를 출력
	cout << "True" << endl;
 
	return 0;
}

문제 2: 전력 공급 §

#include <cstdlib>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <algorithm>
 
using namespace std;
 
int main() {
	// 표준입출력
	string strIn, strNum;
 
	getline(cin, strIn);
	stringstream ss(strIn);
	vector<int> bases;
	while(getline(ss, strNum, ' ')) {
		if(strNum.size() > 0) {
			bases.push_back(stoi(strNum));
		}
	}
 
	getline(cin, strIn);
	stringstream sp(strIn);
	vector<int> powers;
	while(getline(sp, strNum, ' ')) {
		if(strNum.size() > 0) {
			powers.push_back(stoi(strNum));
		}
	}
 
	int nMax = -1;
	for(const auto& base : bases) {
		// base 하나에 대해 가장 가까운 power을 찾음
		int nMin = 1000000;
		for(const auto& power : powers) {
			nMin = min(nMin, abs(base - power));
		}
		// 가장 가까운 power와의 거리들 중 가장 큰 값을 저장함
		nMax = max(nMax, nMin);
	}
 
	cout << nMax << endl;
 
	return 0;
}