백준 1260 - DFS 와 BFS

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

1260번: DFS와 BFS

 

본 문제의 요구사항은 대표적인 그래프의 탐색 방법인 깊이우선 탐색 ( DFS ) 과 너비 우선 탐색( BFS ) 을 구현하여 방문 노드를 순서대로 출력하는 것이다.  단 방문할수 있는 정점이 여러개인 경우 오름차순으로 방문해야 한다.

 

DFS 와 BFS 의 정의는 아래 위키폐이지에 잘 설명되어있다.

DFS : https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

BFS : https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

단순히 탐색하는 코드를 작성할수도 있지만 코드의재사용성 및 확장성을 대비하여 Graph 라는 클래스를 만들고 필요한 인터페이스를 추가해보자.

인터페이스는 아래와 같다

- 초기화 : Node 갯수를 받아서 그래프 자료구조를 초기화 한다.

- 간선연결 : 서로 다른 두 노드간 간선을 연결한다.

- 방문 기록 초기화 : 각 노드들의 방문 기록을 초기화 한다.

- dfs : 깊이 우선 탐색을 하여 방문 노드 순으로 표준출력한다.

- bfs : 너비 우선 탐색을 하여 방문 노드 순으로 표준 출력한다.

- sort_less : 각 노드별 간선으로 이어진 노드들을 오름차순으로 정렬

 

데이터 멤버는 아래와 같다.

- mNodes : 2차원정수형 벡터 자료구조로 각 노드별 연결되는 노드 리스트를 가지고 있다.

- mVisit : 각 노드의 방문기록을 가지고 있다.

 

깊이우선 탐색은 재귀호출을 통하여 방문하지 않은 노드 순서대로 방문하면 된다.

너비우선 탐색은 Queue 를 이용하여 방문할 목록들을 Q 에 넣어놓고 하나씩 꺼내서 방문하면 된다.

 

구현된  Graph 클래스의 코드는 아래와 같다.

 

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

using namespace std;

class Graph
{
private:
	vector<vector<int>> mNodes;
	vector<bool> mVisit;
public:
	Graph(int nrNode) : mNodes(nrNode+1), mVisit(nrNode+1, false){}
	void addEdges(int s, int d)
	{
		mNodes[s].push_back(d);
		mNodes[d].push_back(s);
	}
	void sort_less()
	{
		for_each(mNodes.begin(), mNodes.end(), [](vector<int> &v) {
			sort(v.begin(), v.end(), less<int>());
		});
	}
	void visit_init()
	{
		fill(mVisit.begin(), mVisit.end(), false);
	}
	void dfs(int n)
	{
		printf("%d ", n);
		mVisit[n] = true;
		for_each(mNodes[n].begin(), mNodes[n].end(), [&](int &n){
			if (mVisit[n] == false)
			{
				dfs(n);
			}
		});
	}
	void bfs(int n)
	{
		queue<int> q;
		q.push(n);
		mVisit[n] = true;
		while (!q.empty())
		{
			int c = q.front();
			printf("%d ", c);

			q.pop();
			for_each(mNodes[c].begin(), mNodes[c].end(), [&](int &n){
				if (mVisit[n] == false)
				{
					q.push(n);
					mVisit[n] = true;
				}
			});
		}
	}
};

int main()
{
	int nrV, nrE, s;

	cin >> nrV >> nrE >> s;

	Graph g(nrV);
	for (int i = 0; i < nrE; i++)
	{
		int t1, t2;
		cin >> t1 >> t2;
		g.addEdges(t1, t2);
	}
	g.sort_less();
	g.visit_init();
	g.dfs(s);
	printf("\n");
	g.visit_init();
	g.bfs(s);
	printf("\n");
	return 0;
}