6. DFS, BFS (충남대 알고리즘 강의록)

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

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

문제 1: DFS, BFS 구현하기 §

#include <iostream>
#include <string>
#include <sstream>
#include <map>
#include <queue>
#include <vector>
 
using namespace std;
 
// 방문한 노드를 저장할 배열
int visitedDFS[13] = {};
int visitedBFS[13] = {};
// 방문 결과를 저장할 배열
vector<string> vecDFS;
vector<string> vecBFS;
 
void dfs(map<string, vector<string>> mMap, string cur) {
	// 방분한 노드를 저장
	vecDFS.push_back(cur);
	// 인접노드 배열을 저장
	auto els = mMap[cur];
	// 인접노드를 뒤에서부터 탐색
	for(auto it = els.rbegin(); it != els.rend(); it++) {
		// 만약 방문하지 않은 노드일때
		if(visitedDFS[(*it)[0] - 'A'] != 1) {
			// 방문함으로 바꿔주고
			visitedDFS[(*it)[0] - 'A'] = 1;
			// 다음노드를 방문
			dfs(mMap, *it);
		}
	}
}
 
void bfs(map<string, vector<string>> mMap, string start) {
	// 큐를 생성하고 첫번째 노드를 큐에 넣어줌
	queue<string> q;
	q.push(start);
	visitedBFS[start[0] - 'A'] = 1;
	while(!q.empty()) {
		// 큐의 헤드를 pop하여 현재 노드를 얻어옴
		string h = q.front();
		q.pop();
		// 현재 노드를 방문 목록에 추가함
		vecBFS.push_back(h);
		// 현재 노드와 인접 노드를 순회함
		for(const auto& el : mMap[h]) {
			// 만약 방문하지 않은 노드일때
			if(visitedBFS[el[0] - 'A'] != 1) {
				// 방문함으로 바꿔주고
				visitedBFS[el[0] - 'A'] = 1;
				// 해당 노드를 큐에 넣어줌
				q.push(el);
			}
		}
	}
}
 
int main() {
	string chStart;
	cin >> chStart;
	map<string, vector<string>> mMap;
	
	// input을 받음
	for(int i = 0; i < 13; i++) {
		string line;
		getline(cin, line);
		stringstream ss(line);
		string key, val;
		getline(ss, key, ' ');
		mMap[key] = {};
		while(getline(ss, val, ' ')) {
			mMap[key].push_back(val);
		}
	}
	
	// BFS로 노드들을 순회하여 그의 결과를 저장함
	bfs(mMap, chStart);
 
	// 첫번째 노드를 방문했음으로 바꿔주고 DFS로 노드들을 순회하여 그의 결과를 저장함
	visitedDFS[chStart[0] - 'A'] = 1;
	dfs(mMap, chStart);
	
	// BFS에 대해 방문한 노드들을 출력함
	for(int i = 0; i < 12; i++) {
		cout << vecBFS[i] << ' ';
	}
	cout << vecBFS[12] << endl;
	
	// DFS에 대해 방문한 노드들을 출력함
	for(int i = 0; i < 12; i++) {
		cout << vecDFS[i] << ' ';
	}
	cout << vecDFS[12] << endl;
 
	
	return 0;
}

문제 2: 후플푸프의 컵 §

/**
 * CNU week6
 * 
 * Hufflepuff's cup
 * 
 * DFS
 * 
 * refs: getline + stoi
 */
 
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
 
using namespace std;
 
// 트로피들의 관계를 저장하는 2차원 배열
vector<vector<int>> mMap;
// 방문체크를 위한 배열
bool* visited;
// 트로피의 갯수
int nCups;
 
bool fnVisit(int cur) {
	// 만약 마지막 트로피에 도달하면 참을 반환하고 종료
	if(cur == nCups - 1) {
		return true;
	}
	// 현재의 노드를 방문했음으로 변경함
	visited[cur] = true;
	// 트로피에 담긴 쪽지들을 순회함
	for(const auto& nTicket : mMap[cur]) {
		// 만약 방문하지 않은 트로피가 쪽지에 있으면
		if(!visited[nTicket]) {
			// 해당 트로피를 방문하고 만약 제일 끝까지 도달하였으면 바로 참을 반환하고 종료
			if(fnVisit(nTicket)) {
				return true;
			}
		}
	}
	// 만약 인접한 어느 트로피도 마지막까지 도달하지 못했으면 거짓을 반환하고 종료
	return false;
}
 
int main() {
	// input을 받아옴
	cin >> nCups;
	visited = new bool[nCups];
	string strIn, chIn;
	mMap.reserve(nCups);
	cin.ignore();
	for(int i = 0; i < nCups; i++) {
		visited[i] = false;
		getline(cin, strIn);	
		stringstream ss(strIn);
		vector<int> vecTemp;
		while(getline(ss, chIn, ' ')) {
			if(chIn.size() > 0) {
				vecTemp.push_back(stoi(chIn));
			}
		}
		mMap.push_back(vecTemp);
	}
 
	// 0번 트로피부터 방문하여
	//	 마지막 트로피까지 도달하였으면 True를 출력하고
	//	 도달하지 못하였으면 False를 출력함
	if(fnVisit(0)) {
		cout << "True" << endl;
	} else {
		cout << "False" << endl;
	}
 
	delete visited;
	return 0;
}

문제 3: 독점 무역로 구하기 §

#include <iostream>
#include <vector>
#include <array>
#include <queue>
#include <algorithm>
#include <set>
 
using namespace std;
 
int nCities, nRoads;
 
bool fnVisit(const vector<vector<int>>& vecMap) {
	// 방문체크를 위한 배열 선언
	vector<bool> visited(nCities);
	// 첫번째 노드를 방문함드로 명시
	visited[0] = true;
	// 큐를 생성하고 첫번째 노드를 삽입함
	queue<int> q;
	q.push(0);
	// 큐가 비어있지 않을때까지 반복
	while(!q.empty()) {
		// 큐의 헤드를 받아오고 pop함
		int h = q.front();
		q.pop();
		// 큐와 인접한 노드들을 순회함
		for(const auto& n : vecMap[h]) {
			// 만약 방문하지 않은 인접 노드가 있을때
			if(!visited[n]) {
				// 방문함으로 변경하고
				visited[n] = true;
				// 해당 노드를 큐에 넣어줌
				q.push(n);
			}
		}
	}
	// 모든 노드를 방문하였는지 체크하여
	//	 방문하지 않은 노드가 있으면 단절되었다는 뜻이므로 
	//	 false를 반환하고 종료
	for(const auto& el : visited) {
		if(!el) {
			return false;
		}
	}
	// 모든 노드를 방문하였으면 true를 반환하고 종료
	return true;
}
 
// 도로를 이용해 노드들간의 양방향 그래프를 만들어주는 함수
vector<vector<int>> fnGetConn(const set<array<int, 2>>& vecRoads) {
	// 양방향 그래프를 저장할 배열
	vector<vector<int>> vecMap(nCities);
	// 도로들을 하나씩 순회함
	for(const auto& road : vecRoads) {
		// 양방향 그래프이므로 서로서로 연결되어있다고 명시
		vecMap[road[0]].push_back(road[1]);
		vecMap[road[1]].push_back(road[0]);
	}
	// 양방향 그래프를 반환
	return vecMap;
}
 
int main() {
	// 도로들에 대한 input을 입력받음
	cin >> nCities >> nRoads;
	set<array<int, 2>> vecRoads;
	for(int i = 0; i < nRoads; i++) {
		array<int, 2> road;
		cin >> road[0] >> road[1];
		sort(road.begin(), road.end());
		vecRoads.insert(road);
	}
 
	// 독점 무역로에 대한 집합
	set<array<int, 2>> vecRes;
 
	// 도로들을 하나씩 순회하며
	for(const auto& road : vecRoads) {
		// 도로 목록에 대한 복사본을 생성하고 도로 하나를 제거함
		auto deleted = vecRoads;
		deleted.erase(find(deleted.begin(), deleted.end(), road));
		// 제거된 도로 목록을 이용해 양방향 그래프를 생성
		auto delConn = fnGetConn(deleted);
		// 각 도시들을 순회하여 만약 단절된 도시가 있으면 제거한 도로를 결과에 넣어줌
		if(!fnVisit(delConn)) {
			vecRes.insert(road);
		}
	}
 
	// 독점 무역로 집합을 출력함
	for(const auto& road : vecRes) {
		cout << road[0] << ' ' << road[1] << endl;
	}
 
	return 0;
}