[백준 BOJ] 1260 : DFS와 BFS(C++)

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

1260번: DFS와 BFS

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

bool visited[1001];
vector <int> graph[1001];

// 1. 방문처리
// 2. 현재 노드 출력
// 3. 현재 노드의 인접 노드 개수만큼 반복문 실행
// 4. 반복문에 의한 인접 노드가 방문되지 않았다면 dfs 재귀호출
void dfs(int x) {
	visited[x] = true;
	cout << x << " ";
	for (int i = 0; i < graph[x].size(); i++) {
		int y = graph[x][i];
		if (!visited[y]) dfs(y);
	}
}

// 1. queue에 push
// 2. 방문처리
// 3. q.front() 출력 및 q.pop()으로 빼주기
// 4. 현재 노드의 인접 노드 개수만큼 반복문 실행
// 5. 반복문에 의한 인접 노드가 방문되지 않았다면 queue에 push 후 방문처리
// 6. 3,4,5 과정을 while(!q.empty()) 까지 반복
void bfs(int start) {
	queue <int> q;
	q.push(start);
	visited[start] = true;
	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 (!visited[y]) {
				q.push(y);
				visited[y] = true;
			}
		}
	}
}

int main() {
	int N, M, V;
	cin >> N >> M >> V;

	for (int i = 0; i < M; i++) {
		int v1, v2;
		cin >> v1 >> v2;
		graph[v1].push_back(v2);
		graph[v2].push_back(v1);
	}

	// 인접한 노드가 여러개일 경우 수가 작은 노드부터 방문하기 위해 정렬
	for (int i = 1; i <= N; i++) {
		sort(graph[i].begin(), graph[i].end());
	}

	dfs(V);
	for (int i = 0; i <= N; i++) {
		visited[i] = false;
	}
	cout << "\n";
	bfs(V);
}