알고리즘(C++) / 백준 1260 : DFS와 BFS

1260

boj.kr/1260

1260번: DFS와 BFS

 

문제

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

 

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

 

출력

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

 

코드

//1260 DFS와 BFS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

vector<int>* graph = new vector<int>[1001];
bool visited_DFS[1001];
bool visited_BFS[1001];

//DFS 깊이 우선탐색
void DFS(int v) {
	visited_DFS[v] = true; //방문:ture
	cout << v << " ";

	for (int i = 0; i < graph[v].size(); i++) {
		int next = graph[v][i];
		if (!visited_DFS[next])
			DFS(next);
	}
}

//BFS 넓이 우선탐색
void BFS(int v) {
	visited_BFS[v] = true; //방문:ture
	queue<int> q;
	q.push(v);
	
	while (!q.empty()) {
		v = q.front();
		q.pop();
		cout << v << " ";
		for (int i = 0; i < graph[v].size(); i++) {
			int next = graph[v][i];
			if (!visited_BFS[next]) {
				visited_BFS[next] = true;
				q.push(next);
			}
		}
	}

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, V;
	cin >> N >> M >> V;


	int a, b;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}//그래프 생성
	for (int i = 1; i <= N; i++) {
		sort(graph[i].begin(), graph[i].end());
	} // 정렬

	DFS(V);
	cout << "\n";
	BFS(V);
	cout << "\n";

	return 0;
}

 

설명

정점의 개수, 간선의 개수, 시작할 정점의 번호를 입력받은 후 두 정점을 연결하는 간선을 입력받아 그래프를 구현한다.

vector형인 graph에 그래프를 저장한다. 각 정점에 연결된 정점을 저장해서 그래프를 구현할 수 있다. 

 

• DFS(깊이 우선 탐색)

시작하는 정점을 방문한 후 visited_DFS의 방문한 정점을 true로 저장한 후 출력한다.
정점에 연결되어있는 노드의 개수만큼 반복한다. next가 방문하지 않았다면 next 노드로 이동한다. 
이런 방식으로 DFS를 구현할 수 있다.

 

• BFS(넓이 우선 탐색)

시작하는 정점을 방문한 후 visited_BFS의 방문한 정점을 true로 저장한다. 
BFS는 queue를 사용하여 구현한다.
q에 정점을 push 하고 q가 비어있을때까지 반복한다. v는 q의 가장 앞의 정점이다. v를 출력한다. 정점에 연결되어있는 노드의 개수만큼 반복하고 next가 방문되지 않았다면 q에 push한다. 
이런 방식으로 BFS를 구현할 수 있다.

코드를 다음과 같이 작성하고 디버깅을 해보면 자세한 이동을 확인할 수 있다. 

 

DFS와 BFS의 자세한 설명은 다음에서 설명하였다. 

2021.04.10 - [알고리즘] - 알고리즘 / DFS(Depth First Search), BFS(Breath First Search)

알고리즘 / DFS(Depth First Search), BFS(Breath First Search)

 

결과

 

고찰

처음푸는 그래프 DFS, BFS 문제라 데이터 구조 설계 수업의 강의자료를 참고하였다.

구현하면서 다시 한 번 DFS와 BFS의 구조를 이해하였다.

 

난이도

●○○○○