[C/C++] 백준 1260번 DFS와 BFS

 

 

 

 

 

코드

 

#include <iostream>
#include <algorithm> //sort()
#include <vector>
#include <queue> // 큐 사용
#include <cstring> // memset 

using namespace std;

bool visited[1001];
vector<int> graph[1001]; // index 0은 사용하지 않으므로, 배열을 1개 더 추가 총 1001개

// DFS(깊이우선탐색) -> 재귀함수
void DFS(int startnum) { // 탐색 시작 노드 삽입
	visited[startnum] = true; // 탐색시작노드 방문처리
	cout << startnum << " "; // 방문 노드 출력

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

		int nextnum = graph[startnum][i];

		if (visited[nextnum] != true) { // 방문 true, 미방문 false -> 방문하지 않은 구간만 진행
			DFS(nextnum);
		}
	}
}

// BFS(너비우선탐색) -> 큐
void BFS(int startnum) {
	queue<int> Q;
	memset(visited, false, sizeof(visited)); //false로 모두 변경

	visited[startnum] = true; // 탐색시작노드 방문처리
	Q.push(startnum);

	while (!Q.empty()) {
		int Qfront = Q.front();

		Q.pop();
		cout << Qfront << " ";

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

			int nextnum = graph[Qfront][i];

			if (visited[nextnum] == false) { // 탐색할 부분 아직 미방문일 시
				visited[nextnum] = true; // 탐색 방문 처리
				Q.push(nextnum);
			
			}
		}
	}
}


int main()
{
	int N, M, V,m1,m2; // 정점의 개수 : N, 간선의 개수 M, 탐색을 시작할 정점의 번호 V
	cin >> N >> M >> V;

	for (int i = 0; i < M; i++) { // graph 값 채우기
		cin >> m1 >> m2;

		graph[m1].push_back(m2);
		graph[m2].push_back(m1);

	}

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

		sort(graph[i].begin(), graph[i].end());// 낮은 값부터 탐색을 위한 오름차순 정렬
	}

	DFS(V);
	cout << "\n";
	BFS(V);

	return 0;
}