[백준] 1260 DFS와 BFS - C++

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

---

 

그래프를 입력받고 해당 그래프를 DFS와 BFS로 각각 탐색하면 된다.

DFS와 BFS 모두 공부할 수 있는 기초 문제이기 때문에, 최대한 이해하는 편이 유익하다.

 

---

부분 코드 설명

vector<int> graph[1001];
bool visited_bfs[1001];
bool visited_dfs[1001];

 

노드와 링크 정보를 저장할 graph를 선언한다. 배열의 각각의 원소는 벡터로 존재한다. 배열의 index는 각각의 노드 번호를 가리키고, 배열의 원소인 벡터는 해당 노드와 연결되어 있는 다른 노드의 번호를 저장한다.

이미 탐색한 경로는 다시 탐색하지 않기 위해 bool형 visited 배열을 DFS와 BFS 각각 따로 선언해주었다.

 

int main() {
	int n, m, v;
	cin >> n >> m >> v;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		sort(graph[i].begin(), graph[i].end());
	}
	dfs(v);
	cout << "\n";
	bfs(v);
	cout << "\n";
	return 0;
}

main함수이다.

노드의 개수 n, 링크의 개수 m, 탐색을 시작할 노드의 번호 v를 입력받는다.

 

그 후 m개만큼의 링크를 입력받는데, 위에서 설명했듯 graph는 어떤 노드끼리 연결되어 있는지 그 연결관계를 나타내기 때문에,

u, v 노드가 서로 연결되어 있다면 graph[u]에는 v와 연결되어 있다는 정보를, graph[v]에는 u와 연결되어 있다는 정보를 넣어주어야 할 것이다.

 

노드 번호가 낮은 순서부터 탐색을 하기 때문에, sort 함수를 이용해 graph 속 벡터를 오름차순 정렬해 준다.

 

void dfs(int start) {
	stack<int> s;
	s.push(start);
	while (!s.empty()) {
		int cur = s.top();
		s.pop();
		if (visited_dfs[cur]) {
			continue;
		}
		visited_dfs[cur] = true;
		cout << cur << " ";
		for (int i = graph[cur].size() - 1; i >= 0; i--) { // <1>
			int next = graph[cur][i]; // <2>
			if (!visited_dfs[next]) { // <3>
				s.push(next);
			}
		}
	}
}

DFS를 수행하는 함수이다.

DFS는 stack을 이용하기 때문에 선언해 주고, 시작점인 start를 stack에 push한다.

 

while문 내의 코드를 stack이 빌 때까지 반복한다.

stack에서 값을 하나 꺼내 와 cur에 저장하고, 이미 방문했던 경로라면 continue한다.

아니라면 방문표시하고, 현재 노드를 출력한다.

 

<1> : 현재 노드와 인접한 노드의 수만큼 반복하겠다는 뜻이다. main에서의 sort로 인해 graph는 현재 오름차순 정렬 되어있는 상태이고, stack은 LIFO이기 때문에 낮은 번호를 가진 노드를 가장 나중에 넣어주어야 낮은 번호의 노드부터 탐색을 한다 (문제 조건)

따라서 해당 반복문의 증감식을 마이너스로 잡았다.

<2> : 현재 노드 다음으로 탐색할 노드를 정한다. 현재 노드와 연결되어 있는 노드 중 i번째 노드를 선택한다는 뜻이다.

<3> : 방문하지 않았던 노드만 stack에 push한다. 이 과정이 없으면 방문했던 노드도 다시 탐색하게 되어 영 좋지 않은 결과가 나오게 될 수도 있다..

 

void dfs(int cur) {
	visited_dfs[cur] = true;
	cout << cur << " ";
	for (int next : graph[cur]) {
		if (!visited_dfs[next]) {
			dfs(next);
		}
	}
}

사실 DFS는 재귀로도 구현할 수 있다!!

함수가 호출되면 매개변수로 넘겨받은 노드를 방문처리한다.

for문 괄호 안의 식이 생소할 수 있는데, next라는 변수에 graph[cur]의 값을 하나씩 넣으면서 실행한다는 뜻이다.

next 노드를 방문하지 않았었다면 재귀적으로 자신을 호출해 DFS를 수행한다.

 

개인적으로, 간단한 DFS는 재귀로 구현하는 편이 좀 더 직관적인 것 같다.

 

void bfs(int start) {
	queue<int> q;
	q.push(start);
	visited_bfs[start] = true;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		cout << cur << " ";
		for (int next : graph[cur]) {
			if (!visited_bfs[next]) {
				q.push(next);
				visited_bfs[next] = true;
			}
		}
	}
}

BFS를 수행하는 함수이다.

뭐.........

진짜로 DFS의 큐 버전이다...

 

전체 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
vector<int> graph[1001];
bool visited_bfs[1001];
bool visited_dfs[1001];
void dfs(int start) {
	stack<int> s;
	s.push(start);
	while (!s.empty()) {
		int cur = s.top();
		s.pop();
		if (visited_dfs[cur]) {
			continue;
		}
		visited_dfs[cur] = true;
		cout << cur << " ";
		for (int i = graph[cur].size() - 1; i >= 0; i--) {
			int next = graph[cur][i];
			if (!visited_dfs[next]) {
				s.push(next);
			}
		}
	}
}
void bfs(int start) {
	queue<int> q;
	q.push(start);
	visited_bfs[start] = true;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		cout << cur << " ";
		for (int next : graph[cur]) {
			if (!visited_bfs[next]) {
				q.push(next);
				visited_bfs[next] = true;
			}
		}
	}
}
int main() {
	int n, m, v;
	cin >> n >> m >> v;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		sort(graph[i].begin(), graph[i].end());
	}
	dfs(v);
	cout << "\n";
	bfs(v);
	cout << "\n";
	return 0;
}

---

여러 탐색 알고리즘을 사용해 보며 문제를 다양한 각도로 바라보는 능력을 길러야 할 것 같다.

---