[백준]DFS와 BFS3

백준저지

[DFS와 BFS]https://www.acmicpc.net/problem/1260

전체 코드를 포스팅하려고 한다. 

이전 포스팅에서 DSF와 BSF에 대한 코드를 공개했었는데 그래서 사실 이번 포스팅은 필요없는 부분일지도 모르지만...

힘들게 고민해서 짠것이니...!!

삶을 살아가면서 최고의 순간만 쟁취할 수는 없다.

신중하게 결정하고 생각한다고 해도 당신이 고른 영화가 항상 재밌을 거라는 보장은 없다.

평점을 보고 리뷰를 보고 다른 사람들이 별 다섯 개를 던지며 재밌다고 하는 영화가

당신에게는 별 감흥 없는 영상으로 다가올 수도 있으며,

많은 사람들이 볼 가치도 없는 최악이라고 말하는 영화가

당신의 가슴 깊숙한 부분을 울릴 수도 있다.

아무리 당신이 실패를 예방하기 위해 조심스럽게 산다고 해도

마음처럼 되지 않는 게 당연할 거다.

그러니 최선의 선택이 실패였어도 좌절하지 마라. 그때 그 선택을 후회하지 마라.

실패는 살아가면서 절대 피할 수 없는 것이고,

예상하지 못한 실패가 다가온 것처럼 예상하지 못한 뜻밖의 순간들도

찾아오는 법이니까...

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

/**
* @brief: 정점 출력을 담당하는 함수
* @param: bool visitArr[], int ver
*
* visitArr: 정점에 대해 방문 여부를 나타내는 배열
* ver: 방문할 정점 변수
*/
void VisitVertex(bool visitArr[], int ver) {
	cout << ver << " ";
	visitArr[ver] = true;
}

/**
* @brief: 깊이 우선 탐색
* @param: vector<int> vecArr[], bool visitArr[], int num, int fir
*
* vecArr: 그래프 나타내는 배열(by 인접 리스트)
* visitArr: 카드 섞을 때 중복을 방지하는 기준 배열
* num: 정점의 개수
* fir: 처음 방문할 정점 변수
*/
void ShowDFS(vector<int> vecArr[], bool visitArr[], int num, int fir) {
	stack<int> stack;
	int visit = fir; // 방문 변수 선언

	for (int i = 0; i <= num; i++) // 방문 여부 전부 false
		visitArr[i] = false;

	stack.push(fir); 
	VisitVertex(visitArr, fir); 

	while (!stack.empty()) { // 스택이 비어있지 않는 동안

		bool visitFlag = false; // true: 인접한 정점에 방문, false: 인접한 정점을 모두 방문한 경우

		for (int i = 0; i < (int)vecArr[visit].size(); i++) {
			int next = vecArr[visit][i];
			if (visitArr[next] == false) {
				stack.push(next); 
				VisitVertex(visitArr, next);
				visit = next;
				visitFlag = true;
				break;
			}
		}

		if (visitFlag == false) { // 인접한 정점에 모두 방문을 했으니 가장 가까운 곳으로 가자!
			stack.pop();
			if (!stack.empty()) {
				visit = stack.top();
			}
		}
	}
}

/**
* @brief: 넓이 우선 탐색
* @param: vector<int> vecArr[], bool visitArr[], int num, int fir
*
* vecArr: 그래프 나타내는 배열(by 인접 리스트)
* visitArr: 카드 섞을 때 중복을 방지하는 기준 배열
* num: 정점의 개수
* fir: 처음 방문할 정점 변수
*/
void ShowBFS(vector<int> vecArr[], bool visitArr[], int num, int fir) {
	queue<int> queue;
	int visit = fir;

	for (int i = 0; i <= num; i++)
		visitArr[i] = false;

	queue.push(fir); 
	VisitVertex(visitArr, fir);
	while (!vecArr[visit].empty()) {
		for (int i = 0; i < (int)vecArr[visit].size(); i++) {
			int next = vecArr[visit][i];
			if (visitArr[next] == false) {
				queue.push(next);
				VisitVertex(visitArr, next);
			}
		}
		queue.pop();
		if (!queue.empty()) {
			visit = queue.front();
		} else {
			break;
		}
	}
}

int main(void) {

	int num[3];
	vector<int> vecArr[1001];

	for (int i = 0; i < 3; i++)
		cin >> num[i];

	bool * visitArr = (bool *)malloc(sizeof(bool) * (num[0] + 1)); // 방문 여부를 검사

	for (int i = 0; i < num[1]; i++) {
		int one, two;
		cin >> one >> two;

		vecArr[one].push_back(two);
		vecArr[two].push_back(one);
	}

	for (int i = 1; i <= num[0]; i++) // 정렬하기
		sort(vecArr[i].begin(), vecArr[i].end());

	ShowDFS(vecArr, visitArr, num[0], num[2]);
	cout << endl;
	ShowBFS(vecArr, visitArr, num[0], num[2]);
	cout << endl;
	free(visitArr);
	return 0;
}