C++ 알고리즘 - 백준 1260 DFS와 BFS

https://www.acmicpc.net/problem/1260

 

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

pair<int, bool> vertex[1002];
vector<pair<int, int>> edge;
vector<int> v;
queue<int> bfschk;

void dfs(int start) {
	if (vertex[start].second == true) {
		v.push_back(start);
		vertex[start].second = false;

		for (int i = 0; i < edge.size(); i++) {
			if (edge[i].first == start && vertex[edge[i].second].second == true)
				dfs(edge[i].second);
		}
	}
}

void bfs(int start) {
	if (vertex[start].second == true) {
		v.push_back(start);

		for (int i = 0; i < edge.size(); i++) {
			if (edge[i].first == start && vertex[edge[i].second].second == true)
				bfschk.push(edge[i].second);
		}
	}

	vertex[start].second = false;

	if (bfschk.size() > 0) {
		int num = bfschk.front();
		bfschk.pop();
		bfs(num);
	}
}

bool compare(pair<int, int> x, pair<int, int> y) {
	if (x.first == y.first)
		return x.second < y.second;
	else
		return x.first < y.first;
}

int main(void) {
	/************** C++ Init **************/
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	/************** C++ Init **************/


	int input1, input2, input3;
	int x, y;
	cin >> input1 >> input2 >> input3;

	for (int i = 1; i <= input1; i++) {
		vertex[i] = { i, true };
	}

	for (int i = 0; i < input2 * 2; i += 2) {
		cin >> x >> y;
		edge.push_back({ x,y });
		edge.push_back({ y,x });
	}

	sort(edge.begin(), edge.end(), compare);

	dfs(input3);
	for (int i = 0; i < v.size(); i++) {
		if (i == v.size() - 1)
			cout << v[i];
		else
			cout << v[i] << " ";
	}

	cout << endl;

	v.clear();
	for (int i = 1; i <= input1; i++) {
		vertex[i] = { i, true };
	}

	bfs(input3);
	for (int i = 0; i < v.size(); i++) {
		if (i == v.size() - 1)
			cout << v[i];
		else
			cout << v[i] << " ";
	}
}

 

 

DFS는 재귀함수

BFS는 재귀함수 + 큐