[Algorithm][C++] BFS/DFS

< BFS(Breath First Search): 너비 우선 탐색 >

 

Queue와 방문노드를 체크할 배열을 이용하여 코딩할 수 있습니다.

(Queue는 선입선출 구조를 갖는 자료구조로, 먼저 넣은 값을 먼저 사용합니다. 따라서 넓게 탐색해야하는 BFS로 적절한 방법입니다)

 

1. queue에 0번 노드를 넣습니다.

int visit []

0

0

0

0

0

queue<int>

0

 

2. 한번 방문한 노드는 다시 방문하지 않기 위해 visit 배열에 현재노드를 체크합니다.

 

int visit []

1

0

0

0

0

0

queue<int>

0

 

3. queue의 첫번째 값인 0번노드를 빼서 탐색합니다.

즉, 0번 노드의 이웃 노드인 1번, 2번 노드가 방문된 적이 있는지를 확인하고

방문한 적이 없으면 queue에 삽입하고 방문노드로 체크합니다.

 

int visit []

1

1

1

0

0

0

queue<int>

1

2

 

4. queue의 맨 앞 값인 1번 노드를 빼서 탐색합니다.

1번 노드의 이웃노드(3, 4)를 방문한 적이 없으면 queue에 삽입하고 방문노드로 체크합니다.

 

int visit []

1

1

1

1

1

0

queue<int>

2

3

4

 

5. queue가 빌 때까지 위의 과정을 반복합니다.

 

[ C++ 코드 ]

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

vector<int> v[1001];
int visit_bfs[1001] = { 0, };

void bfs(int s) {
	queue<int> q;
	q.push(s); //큐에 넣고
	visit_bfs[s] = true; //방문노드로 체크

	while (!q.empty()) { //큐가 모두 비워질 때 까지
		int x = q.front(); //큐의 맨 첫번째 값을 빼서 확인
		q.pop(); //큐에서 제거
		cout << x << " ";
		for (int i = 0; i < v[x].size(); i++) //현재노드에 연결된 노드의 크기까지
		{
			int y = v[x][i]; //인접노드 값을 저장
			if (!visit_bfs[y]) { //인접노드가 방문 안한 노드이면
				q.push(y); //큐에 삽입
				visit_bfs[y] = true; //방문노드로 체크
			}
		}
	}
}

int main() {
	int V, E, S; //노드, 엣지, 시작노드
	cin >> V >> E >> S;

	int v1, v2;
	for(int i = 1; i <= E; i++) {
		cin >> v1 >> v2; //연결된 노드 정보를 입력하면 벡터로 연결하기
		v[v1].push_back(v2);
		v[v2].push_back(v1);
	}
	for (int i = 1; i < V; i++) { //오름차순 정렬
		sort(v[i].begin(), v[i].end());
	}
	bfs(S);
}

 

 

< DFS(Depth First Search): 깊이 우선 탐색 >

 

Stack or 재귀호출과 방문노드를 체크할 배열 이용

(방문한 노드에 이웃노드가 없을 때까지 깊이 있게 탐색해야 하므로 후입선출 구조를 가진 Stack or 재귀호출을 이용하는 것입니다)

 

1. 스택에 0번 노드(시작노드)를 삽입하고, 0번 노드를 방문노드로 체크합니다.

 

int visit []

1

0

0

0

0

0

stack <int>

0

 

2. 0번 노드에 이웃노드 1, 2가 있으므로 우선순위에 의해 stack에 1번을 삽입하고 방문노드로 체크합니다.

 

int visit []

1

1

0

0

0

0

stack <int>

0

1

 

3. 1번 노드에 이웃한 노드인 3, 4가 있으므로 우선순위에 의해 3번을 stack에 넣고 방문노드로 체크합니다.

 

int visit []

1

1

0

1

0

0

stack <int>

0

1

3

 

4. 3번노드에 이웃한 노드가 없으므로 3번노드를 stack에서 pop하여 방문하지 않은 인접노드가 있는지 확인합니다.

 

int visit []

1

1

0

1

0

0

stack <int>

0

1

 

5. 1번노드에 이웃한 노드가 없으므로 1번노드를 stack에서 pop하여 방문하지 않은 인접노드가 있는지 확인합니다.

 

int visit []

1

1

0

1

0

0

stack <int>

0

 

6. 0번 노드에 방문하지 않은 이웃노드 2가 있으므로 stack에 2번을 삽입하고 방문노드로 체크합니다.

 

int visit []

1

1

1

1

0

0

stack <int>

0

2

 

7. stack이 빌 때까지 위의 과정을 반복합니다.

 

[ C++ 코드 ]

1) Stack을 이용한 방법

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

vector<int> v[1001];//노드 정보를 담을 변수
int visit_dfs[1001] = { 0, };//방문여부를 담을 변수

void dfs(int s) {
	stack<int> stk;

	visit_dfs[s] = true;//시작노드 방문표시!
	stk.push(s);  //stack에 삽입

	cout << s << " ";

	while (!stk.empty()) { //stack이 빌 때까지 반복
		int x = stk.top(); //stack의 맨 위 노드 값을 탐색
		stk.pop(); //맨 위 노드 버리기

		for (int i = 0; i < v[x].size(); i++) //x의 이웃노드의 개수까지 반복
		{
			int y = v[x][i]; //이웃노드를 y로 지정
			if (!visit_dfs[y]) { //y를 방문한적이 없으면
				cout << y << " ";
				visit_dfs[y] = true; //방문했다고 체크
				stk.push(x); //pop했었기 때문에 다시 stack에 x 삽입해서 검사(x의 이웃노드의 개수까지 반복해야하니깐)
				stk.push(y); //stack에 y도 삽입
				break;
			}
		}
	}
}

int main() {
	int V, E, S;//노드, 엣지, 시작노드
	cin >> V >> E >> S;

	int v1, v2;
	for (int i = 1; i <= E; i++) {//연결된 노드정보를 입력하면 벡터로 이어주기
		cin >> v1 >> v2;
		v[v1].push_back(v2);
		v[v2].push_back(v1);
	}
	for (int i = 1; i < V; i++) {//오름차순 정렬
		sort(v[i].begin(), v[i].end());
	}
	dfs(S);
}

 

 

 

2) 재귀호출을 이용한 방법

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

vector<int> graph[1001];
bool check[10001];

void dfs(int v) {
	check[v] = true;//방문노드로 체크
	cout << v << " ";

	for (int i = 0; i < graph[v].size(); i++) {//이웃 노드 탐색
		int next = graph[v][i];
		if (check[next] == false) {//이웃 노드가 방문안한 노드라면
			dfs(next);//그 노드를 방문함으로써 DFS탐색!
		}
	}
}

int main() {
	int V, E, S; //간선 수, 엣지 수, 시작노드
	cin >> V >> E >> S;

	int v1, v2;
	for (int e = 0; e < E; e++) {//노드 연결
		cin >> v1 >> v2;
		graph[v1].push_back(v2);
		graph[v2].push_back(v1);
	}
	for (int i = 1; i <= V; i++) {//순차적인 노드접근을 위해 오름차순 정렬해주기
		sort(graph[i].begin(), graph[i].end());
	}
	dfs(S);
}