백준 1260 (DFS와 BFS)

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

1260번: DFS와 BFS

해당 문제는 N개의 정점이 주어지면 해당 정점들의 간선의 정보가 주어지면 해당 정점들의 간선을 통해 연결 되어 있는 정점들을 DFS, BFS로 탐색을 하며 탐색되는 각 정점을 출력하는 문제이다.

이때 하나의 정점에 연결 된 간선이 여러개라면 숫자가 작은 정점을 방문하는 조건이 있다.

주의 사항 :

하나의 정점에 간선이 여러개일 경우 숫자가 작은 정점부터 방문해야 하기때문에 입력을 받을 때 해당 정점을 오름차 순으로 정렬을 시켜 두면 방문할때 작은 숫자부터 탐색을 진행할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int n, m, v;
vector<int> map[1001];
int usedBfs[1001];
int usedDfs[1001];

void dfs(int v){

	cout << v << ' ';

	for (int i = 0; i < map[v].size(); ++i){
		if (usedDfs[map[v][i]] == 1) continue;
		usedDfs[map[v][i]] = 1;
		dfs(map[v][i]);
	}
}

void bfs(int v){
	queue<int> qu;
	qu.push(v);
	usedBfs[v] = 1;
	int tmp;
	while (!qu.empty()){
		int now = qu.front();
		cout << now << ' ';
		for (int i = 0; i < map[now].size(); ++i){
			if (usedBfs[map[now][i]] == 1) continue;
			usedBfs[map[now][i]] = 1;
			qu.push(map[now][i]);
		}
		qu.pop();
	}
	printf("\n");
	return;
}

int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> n >> m >> v;

	for (int i = 0; i < m; ++i){
		int a, b;
		cin >> a >> b;
		map[a].push_back(b);
		map[b].push_back(a);
        // 정렬을 수행하여 작은 정점을 먼저 방문하도록 한다.
		sort(map[a].begin(), map[a].end());
		sort(map[b].begin(), map[b].end());
	}
	
	usedDfs[v] = 1;
	dfs(v);
	printf("\n");
	bfs(v);

}