[C++] 백준 1260 : DFS와 BFS

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

1260번: DFS와 BFS

 

백준 1260번 DFS와 BFS를 풀어봤습니다.

간단한 그래프 탐색 방법인 DFS와 BFS를 같이 사용하는 문제입니다.

 

아래는 전체 코드입니다.

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

bool visited[1001];	// For DFS
bool visited2[1001];	// For BFS
vector<int> graph[1001];	// Graph
queue<int> q;	// For BFS

void DFS(int v);
void BFS(int v);

int main() {
	int n, m, start;
	cin >> n >> m >> start;
	
	for (int i = 0; i < m; i++) {
		int temp1, temp2;
		cin >> temp1 >> temp2;
		
		// Two-way edge
		graph[temp1].push_back(temp2);
		graph[temp2].push_back(temp1);
	}

	for (int i = 0; i < 1001; i++) {
		if (graph[i].size() != 0) {

			// Sort and remove duplicate numbers
			sort(graph[i].begin(), graph[i].end());
			graph[i].erase(unique(graph[i].begin(), graph[i].end()), graph[i].end());

			// To check the results of sorting and deleting
			//for (int j = 0; j < graph[i].size(); j++) {
			//	cout << i << ' ' << graph[i][j] << " \n";
			//}
		}
	}

	DFS(start);
	cout << '\n';

	BFS(start);
	cout << '\n';

	return 0;
}

void DFS(int v) {
	if (visited[v] == 0) {
		visited[v] = 1;
		cout << v << ' ';
		for (int i = 0; i < graph[v].size(); i++) {
			int next = graph[v][i];
			DFS(next);
		}
	}
}

void BFS(int v) {
	q.push(v);
	visited2[v] = 1;

	while (!q.empty()) {
		int x = q.front();
		q.pop();
		cout << x << ' ';
		for (int i = 0; i < graph[x].size(); i++) {
			int y = graph[x][i];
			if (visited2[y] == 0) {
				q.push(y);
				visited2[y] = 1;
			}
		}
	}

}