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

1. 문제 링크

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

 

 

2. 문제 설명

정점의 개수, 간선의 개수, 탐색을 시작할 정점의 번호, 간선이 연결하는 두 정점의 번호를 입력받아서

DFS를 수행한 결과와 BFS를 수행한 결과를 출력하는 문제입니다.

방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 합니다.

 

 

 

3. 소스코드

BOJ 1260번 DFS와 BFS C++ 풀이입니다.

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

vector<int> e[1001];
bool check[1001];

void dfs(int v) {
	check[v] = true;
	cout << v << " ";
	for (int i = 0; i < e[v].size(); i++) {
		int next = e[v][i];
		if (!check[next])
			dfs(next);
	}
}

void bfs(int v) {
	queue<int> q;
	q.push(v);
	check[v] = true;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		cout << cur << " ";
		for (int i = 0; i < e[cur].size(); i++) {
			int next = e[cur][i];
			if (!check[next]) {
				check[next] = true;
				q.push(next);
			}
		}
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M, V, from, to;
	cin >> N >> M >> V;
	for (int i = 0; i < M; i++) {
		cin >> from >> to;
		e[from].push_back(to);
		e[to].push_back(from);
	}

	for (int i = 1; i <= N; i++)
		sort(e[i].begin(), e[i].end());
	dfs(V);
	cout << '\n';
	memset(check, false, sizeof(check));
	bfs(V);

	return 0;
}

8번 라인 : 인접 리스트를 저장할 vector를 정점의 최대 개수가 1000이므로 e[1000]으로 접근할 수 있도록 1001의 크기로 선언했습니다.

9번 라인 : 정점의 방문을 체크할 배열 check도 마찬가지 이유로 1001의 크기로 선언했습니다.

45 ~ 49번 라인 : 입력으로 주어지는 간선은 양방향이므로 인접 리스트에 양방향으로 저장합니다.

51 ~ 52번 라인 : 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 하기 때문에 오름차순으로 정렬합니다.

53번 라인 : 탐색을 시작할 정점 V를 넘겨주면서 dfs 함수를 호출합니다.

11 ~ 19번 라인 : 재귀함수를 이용한 dfs입니다.

12번 라인 : 정점을 방문할 때 마다 check[v]를 true로 바꿔주면서 방문한 것을 표시하고,

13번 라인 : 해당 정점을 출력합니다.

14번 라인 : 다음에 방문할 정점을 찾기 위해 현재 방문한 정점과 이어져 있는 정점의 개수만큼 for문을 돌면서,

15번 라인 : next변수에 현재 방문한 정점과 이어져 있는 정점을 저장하고,

16번 라인 : next정점을 방문한 적이 없으면(check[next] == false)

17번 라인 : next정점을 넘겨주면서 dfs 함수를 호출합니다.

55번 라인 : check 배열을 다시 false로 초기화하기 위해 memset함수를 이용합니다.

56번 라인 : 탐색을 시작할 정점 V를 넘겨주면서 bfs 함수를 호출합니다.

21 ~ 37번 라인 : queue를 이용한 bfs입니다.

23번 라인 : 처음 방문한 정점 v를 q에 push합니다.

25번 라인 : 처음 방문한 정점을 표시하기 위해 check[v]를 true로 바꿔줍니다.

25번 라인 : q가 비어있지 않는 동안

26번 라인 : cur변수에 현재 방문한 정점을 q.front()를 이용하여 저장하고,

27번 라인 : q.pop()을 이용하여 q에서 빼주고,

28번 라인 : 현재 방문한 정점을 출력합니다.

29번 라인 : 다음에 방문할 정점을 찾기 위해 현재 방문한 정점과 이어져 있는 정점의 개수만큼 for문을 돌면서,

30번 라인 : next변수에 현재 방문한 정점과 이어져 있는 정점을 저장하고,

31번 라인 : next정점을 방문한 적이 없으면(check[next] == false)

32번 라인 : next정점을 방문하였다고 표시한 후(check[next] = true)

33번 라인 : q에 next정점을 push합니다.