10. 트리 (충남대 알고리즘 강의록)

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

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

문제 1: 트리 순회 §

#include <iostream>
#include <map>
#include <array>
 
using namespace std;
 
map<char, array<char, 2>> conn;
 
// 전위순회
void post(const char& cur) {
	if(conn[cur][0] != '.') { post(conn[cur][0]); } // 첫번째 자식 방문
	if(conn[cur][1] != '.') { post(conn[cur][1]); } // 두번째 자식 방문
	cout << cur; // 자기자신 방문
}
 
// 후위순회
void pre(const char& cur) {
	cout << cur; // 자기자신 방문
	if(conn[cur][0] != '.') { pre(conn[cur][0]); } // 첫번째 자식 방문
	if(conn[cur][1] != '.') { pre(conn[cur][1]); } // 두번째 자식 방문
}
 
// 중위순회
void in(const char& cur) {
	if(conn[cur][0] != '.') { in(conn[cur][0]); } // 첫번째 자식 방문
	cout << cur; // 자기자신 방문
	if(conn[cur][1] != '.') { in(conn[cur][1]); } // 두번째 자식 방문
}
 
int main() {
	int N;
	cin >> N;
	
	for(int i = 0; i < N; i++) {
		char f, s, t;
		cin >> f >> s >> t;
		conn[f] = { s, t };
	}
 
	pre('A');
	cout << endl;
	in('A');
	cout << endl;
	post('A');
	cout << endl;
 
	return 0;
}

문제 2: 공통 지역 찾기 §

#include <iostream>
#include <map>
#include <string>
#include <sstream>
#include <set>
 
using namespace std;
 
int main() {
	// 노드의 갯수
	int N;
	cin >> N;
 
	// 두개의 구 를 입력받음
	string node1, node2;
	cin >> node1 >> node2;
 
	map<string, set<string>> conn;
	set<string> districts;
	cin.ignore();
 
	string strIn, key, value, nation;
	for(int i = 0; i < N; i++) {
		getline(cin, strIn);
		stringstream ss(strIn);
 
		// 국가 혹은 도시를 입력받음
		getline(ss, key, ' ');
 
		// 국가인 경우 국가명을 별도로 저장함
		if(i == 0) {
			nation = key;
		}
 
		// 국가 혹은 도시에 포함된 것을 입력받음
		while(getline(ss, value, ' ')) {
			if(value.size() > 0) {
				conn[key].insert(value);
				districts.insert(value);
			}
		}
	}
 
	// 입력된 구가 국가 내에 존재하지 않는 구일 경우
	if(districts.count(node1) == 0 || districts.count(node2) == 0) {
		cout << 0 << endl;
		return 0;
	}
 
	string city1, city2;
	for(auto it = conn.begin(); it != conn.end(); it++) {
		// 국가-도시 쌍일 경우에는 무시
		if(it->first == nation) {
			continue;
		}
		// 첫번째로 입력받은 구가 현재의 도시에 포함될 경우
		if(it->second.count(node1) == 1) {
			city1 = it->first;
		}
		// 두번째로 입력받은 구가 현재의 도시에 포함될 경우
		if(it->second.count(node2) == 1) {
			city2 = it->first;
		}
	}
 
	if(node1 == node2) {
		// 같은 구일 경우
		cout << node1 << endl;
	} else if(city1 == city2) {
		// 같은 도시에 포함되어있는 구일 경우
		cout << city1 << endl;
	} else {
		// 같은 도시에 포함되어있지 않는 구일 경우
		cout << nation << endl;
	}
}

문제 3: 가까운 노드 값 찾기 §

#include <iostream>
#include <vector>
#include <cmath>
 
using namespace std;
 
int main() {
	int N;
	cin >> N;
 
	// i번째 인덱스의 첫번째 자식은 2 * i + 1 인덱스 이고, 두번째 자식은 2 * i + 2 인덱스가 되게끔 트리를 구성
	vector<int> bst(N);
	for(int i = 0; i < N; i++) {
		cin >> bst[i];
	}
 
	double target;
	cin >> target;
 
	int k;
	cin >> k;
 
	int rounded = round(target);
	int l = rounded - 1, r = rounded + 1;
	vector<int> res(k);
	res[0] = rounded;
	// 노드가 1부터 시작하기 때문에 target이 1보다 작을 경우에 가까운 노드는 1부터 k개의 노드이다
	if(target < 1) {
		for(int i = 0; i < k; i++) {
			res[i] = i + 1;
		}
	} else if(rounded < target) {
		// target이 n.5보다 작을 경우에는 n부터 n + 1, n - 1, n + 2 ... 의 순서대로 가까운 노드가 된다
		for(int i = 1; i < k; i++) {
			if(i % 2 == 0) {
				res[i] = l--;
			} else {
				res[i] = r++;
			}
		}
	} else {
		// target이 n.5보다 클 경우에는 n + 1부터 n, n + 2, n - 1 ... 의 순서대로 가까운 노드가 된다
		for(int i = 1; i < k; i++) {
			if(i % 2 == 0) {
				res[i] = r++;
			} else {
				res[i] = l--;
			}
		}
	}
 
	for(int i = 0; i < k - 1; i++) {
		cout << res[i] << ' ';
	}
	cout << res.back() << endl;
 
	return 0;
}