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

 

알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

문제 링크: https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

 

【 풀이 】

 

정점, 간선, 번호가 순서대로 주어지면 DFS와 BFS로 정점 방문 순서를 출력하면 되는 문제이다.

 

단 주의해야 할 점은 DFS와 BFS를 구현하기 전에, 인접리스트를 사용하였다면 인접리스트를 정렬해 주는 작업이 필요한데,

이는 정점 번호가 더 작은 순부터 차례대로 탐색을 시작하기 때문이다.

또한 DFS와 BFS 사이에는 꼭 방문 배열을 한번 초기화해주는 것이 중요하다.

 

 

 

【 코드 】

 

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

bool isVisited[1001];
vector<int>map[1001];
queue<int>q;
void init(int n) {		//	isVisited 초기화
	for (int i = 0; i <= n; i++) {
		isVisited[i] = false;
	}
}
void form(int n) {		//	인접리스트 정렬
	for (int i = 0; i <= n; i++) {
		sort(map[i].begin(), map[i].end());
	}
}
void dfs(int x) {
	isVisited[x] = true;
	cout << x << " ";
	for (int i = 0; i < map[x].size(); i++) {
		int y = map[x][i];
		if (!isVisited[y])
			dfs(y);
	}
}
void bfs(int x) {
	isVisited[x] = true;
	q.push(x);
	while (!q.empty()) {
		int y = q.front();
		q.pop();
		cout << y << " ";
		for (int i = 0; i < map[y].size(); i++) {
			int z = map[y][i];
			if (!isVisited[z]) {
				isVisited[z] = true;
				q.push(z);
			}
		}
	}
}
int main(void) {
	int n, m, v;
	cin >> n >> m >> v;
	for (int i = 0; i < m; i++) {
		int n1, n2;
		cin >> n1 >> n2;
		map[n1].push_back(n2);
		map[n2].push_back(n1);
	}
	form(n);
	dfs(v);	cout << '\n'; init(n);
	bfs(v);
	return 0;
}