[Graph] BOJ 1260 : DFS 와 BFS

백준 알고리즘 강의를 토대로 작성된 문제풀이입니다.
DFS 와 BFS 의 개념에 대해서는 지난 포스트를 봐주세요.
DFS : 2019/05/23 - [프로그래밍/알고리즘] - [알고리즘] 깊이 우선 탐색(DFS, Depth-First Search)
BFS : 2019/05/26 - [프로그래밍/알고리즘] - [알고리즘] 너비 우선 탐색(BFS, Breadth-First Search)

 

문제

---

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

---

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

 

출력

---

첫째 줄에 DFS를 수행한 결과를, 그다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

풀이

---

 

 

 

지난 포스트에서 이미 개념 설명을 했으니

상세한 개념 설명은 생략하겠습니다.

 

 

그런데 지난 글에서 구현까지 끝낸 개념을 왜 또 포스트 하죠???

라고 생각하실 수 있습니다.

이건 저의 개인적인 느낌인데 BFS 와 DFS 의 개념과 구현을 하면서

"코딩 테스트를 할 때에도 이걸 다 구현해야 하나?"

라는 생각이 들더군요.

 

 

이런 고민을 하고 있을 때, 백준 선생님이 해답을 주셨습니다.ㅎ

문제를 풀 때에는 그래프 구조체나 연결 리스트 등을 굳이 사용할 필요가 없었습니다.

사실, 이건 단지 구현 방법의 차이입니다.

 

 

이 방법으로 코드를 구현하면 굉장히 간략하게 구현이 가능합니다.

이번 포스팅은 BFS 와 DFS를 실전 알고리즘에서 사용하는 코드를 알아보는 것이었습니다. 

 

 

 

 

코드

---

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

using namespace std;
vector<int> a[1001];
//정점과 해당 정점의 인접 리스트들을 저장할 배열
bool check[1001];
//탐색을 하였는지 체크하는 배열

void dfs(int node) { //입력되는 node 부터 탐색시작
	check[node] = true; 
	cout << node << ' ';
	for (int i = 0; i < a[node].size(); i++) {
		//a[node].size 는 해당 노드의 간선의 개수가 된다.
		int next = a[node][i];
		//첫번째 간선으로 이동한 d next에 저장한다.
		if (check[next] == false) {
			//해당 노드를 탐색하지 않았다면 해당 노드에서 다시 dfs
			dfs(next);
		}
	}
}
void bfs(int start) {
	queue<int> q; //인접 노드들이 저장될 큐
	memset(check, false, sizeof(check));
	//dfs 먼저 사용하여 순회를 하기 때문에
	//check 배열을 초기화 시켜준다.
	// 1. 배열주소 2. 초기화 하고 싶은 값 3. 배열의 크기

	check[start] = true;
	q.push(start);
	//탐색을 했다고 체크를 한 후 큐에 넣는다.

	while (!q.empty()) {
		int node = q.front();
		q.pop();
		//가장 먼저 들어온 값을 pop 한후 출력
		cout << node << ' ';
		for (int i = 0; i < a[node].size(); i++) {
			//인접한 노드의 개수만큼 순환
			int next = a[node][i];
			if (check[next] == false) {
				check[next] = true;
				q.push(next);
				// 시작 노드의 인접한 노드들을 전부 큐에 넣는 과정
			}
		}
		// 다 넣었으면 하나씩 pop하면서 노드를 출력한다.
	}
}
int main() {
	int n, m, start;
	cin >> n >> m >> start;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		sort(a[i].begin(), a[i].end());
	}
	dfs(start);
	puts("");
	bfs(start);
	puts("");
	return 0;
}