[백준] Class3-DFS와 BFS C++ 1260번

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

1260번: DFS와 BFS

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Graph
{
public:
	Graph()
	{
		cin >> n >> m >> v;
		k = new int* [n + 1] {};
		for (int i = 0; i < n + 1; i++)
			k[i] = new int[n + 1] {};

		visit1 = new int[n + 1] {};
		visit1[v] = 1;
		visit2 = new int[n + 1] {};
		visit2[v] = 1;

		int a, b;
		while (m--)
		{
			cin >> a >> b;
			k[a][b] = 1;
			k[b][a] = 1;
		}
	}
	~Graph()
	{
		for (int i = 0; i < n; i++)
			delete[] k[i];
		delete[] visit1;
		delete[] visit2;
	}
	void DFS(int x)
	{
		cout << x << ' ';

		for (int i = 1; i <= n; i++)
		{
			if (k[x][i] > 0 && visit1[i] == 0)
			{
				visit1[i] = 1;
				DFS(i);
			}
		}
	}
	void BFS()
	{
		q.push(v);

		while (!q.empty())
		{
			int f = q.front();
			for (int i = 1; i <= n; i++)
			{
				if (k[f][i] > 0 && visit2[i] == 0)
				{
					visit2[i] = 1;
					q.push(i);
				}
			}
			cout << f << ' ';
			q.pop();
		}
	}
	void Print()
	{
		DFS(v);
		cout << '\n';
		BFS();
	}

private:
	int n, m, v;
	int** k;
	int* visit1;
	int* visit2;
	queue<int> q;
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	Graph g;
	g.Print();

	return 0;
};

//2024.04.01 재풀이
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, m, v;
bool visitDFS[1001] = {};
bool visitBFS[1001] = {};
queue<int> q;

void dfs(int num, vector<vector<int>>& k)	//num는 시작할 정점의 번호
{
	cout << num << ' ';
	visitDFS[num] = 1;
	for (int i = 0; i < k[num].size(); i++)
	{
		if (k[num][i] == 1 && visitDFS[i] == 0)
		{
			dfs(i, k);
		}
	}
}

void bfs(int num, vector<vector<int>>& k)
{
	q.push(num);
	visitBFS[num] = 1;

	while (!q.empty())
	{
		for (int i = 0; i < k[num].size(); i++)
		{
			if (k[q.front()][i] == 1 && visitBFS[i] == 0)
			{
				q.push(i);
				visitBFS[i] = 1;
			}
		}
		cout << q.front() << ' ';
		q.pop();
	}
	
	cout << '\n';
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m >> v;
	vector<vector<int>> k(n + 1, vector<int>(n + 1));

	int a, b;

	while (m--)
	{
		cin >> a >> b;
		k[a][b] = 1;
		k[b][a] = 1;
	}

	dfs(v, k);
	cout << '\n';
	bfs(v, k);
}