백준_1260_DFS와BFS

C++ 사용하기

자료형 vector 사용하기

방법1. BFS - 반복문을 이용해서 구현해보기

방법2. BFS - 재귀함수를 이용해서 구현해보기

방법1 코드.

// c++ 쓰기
// vector 쓰기 - 2차원 배열

#include
#include //memset
#include
#include
#include
using namespace std;

vector< vector> arr(10001); //arr[10001][]
int n, m, v; // 정점개수, 간선개수, 탐색시작번호
int visited[1001] = { 0, }; // 0: 방문 안함
                            // 1: 방문 함
int cnt = 0; // 방문 정점 개수
vector stack;
queue que;

void dfs(int idx);
void bfs(int idx);

int main(void) {

	cin >> n >> m >> v;

	for (int i = 0; i < m; i++) {
		int dep, des;
		cin >> dep >> des;
		arr[dep].push_back(des);
		arr[des].push_back(dep);
	}
	
	// 각 정점에 연결된 정점들 오름차순으로 정렬
	for (int i = 1; i <= n; i++) {
		sort(arr[i].begin(),arr[i].end());  
	}

	dfs(v);
	cout << endl;
	memset(visited,0,sizeof(visited));
	cnt = 0;
	bfs(v);

	return 0;
}

void dfs(int idx) {

	cout << idx << " "; // 출력
	visited[idx] = 1; // 방문 표시

	if (cnt++ == n) { // 모두 방문
		return;
	}

	int size = arr[idx].size();
	for (int i = 0; i < size; i++) {
		int temp = arr[idx][i];
		if (visited[temp]==0) { // 방문 안했으면 go
			dfs(temp);
		}
	}
}

void bfs(int idx) {

	que.push(idx);
	cout << idx << " "; //출력
	visited[idx] = 1; //방문 표시

	while (!que.empty()) {
		int _idx = que.front();
		que.pop();

		int size = arr[_idx].size();
		for (int i = 0; i < size; i++) {  // 처음부터 방문
			int temp = arr[_idx][i];
			if (visited[temp] == 0) { //방문 안했으면 push
				cout << temp << " "; //출력
				visited[temp] = 1; //방문 표시
				que.push(temp);
			}
		}
	}
}

방법2 코드.

// c++ 쓰기

// vector 쓰기 - 2차원 배열



// queue 사용

#include

#include //memset

#include

#include

#include

using namespace std;



vector< vector> arr(10001); //arr[10001][]

int n, m, v; // 정점개수, 간선개수, 탐색시작번호

int visited[1001] = { 0, }; // 0: 방문 안함

							// 1: 방문 함

int cnt = 0; // 방문 정점 개수

vector stack;

queue que;



void dfs(int idx);

void bfs(int idx);



int main(void) {



	cin >> n >> m >> v;



	for (int i = 0; i < m; i++) {

		int dep, des;

		cin >> dep >> des;

		arr[dep].push_back(des);

		arr[des].push_back(dep);

	}



	// 각 정점에 연결된 정점들 오름차순으로 정렬

	for (int i = 1; i <= n; i++) {

		sort(arr[i].begin(), arr[i].end());

	}



	dfs(v);

	cout << endl;

	memset(visited, 0, sizeof(visited));

	cnt = 0;

	bfs(v);



	return 0;

}



void dfs(int idx) {



	cout << idx << " "; // 출력

	visited[idx] = 1; // 방문 표시



	if (cnt++ == n) { // 모두 방문

		return;

	}



	int size = arr[idx].size();

	for (int i = 0; i < size; i++) {

		int temp = arr[idx][i];

		if (visited[temp] == 0) { // 방문 안했으면 go

			dfs(temp);

		}

	}

}



void bfs(int idx) {



	if (visited[idx] == 0) { // 방문 안했을 때만

		cnt++;

		cout << idx << " "; //출력

		visited[idx] = 1; //방문 표시

	}



	int size = arr[idx].size();

	for (int i = 0; i < size; i++) {  // 처음부터 방문

		int temp = arr[idx][i];

		if (visited[temp] == 0) { //방문 안했으면 push

			cout << temp << " "; //출력

			visited[temp] = 1; //방문 표시

			que.push(temp);

		}

	}

	// pop

	if (que.empty()) {

		return;

	}

	else {

		int temp = que.front();

		que.pop();

		bfs(temp);

	}

}