[Baekjoon] 1260번: DFS와 BFS

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

1260번: DFS와 BFS

 

---

 

문제 해결 과정

착안

문제에서 주어지는 간선 정보를 바탕으로 깊이 우선 탐색(depth-first search, DFS)과 너비 우선 탐색(breadth-first search, BFS) 알고리즘을 구현하는 것을 요구하는 문제이므로, 두 알고리즘의 특징에 유의하여 구현하고자 하였다.

 

깊이 우선 탐색 알고리즘은 스택(stack) 자료 구조를 활용하여 구현(또는 이전 포스트와 같이 재귀를 통해 구현)할 수 있다. 단, 스택 자료 구조의 FILO(first-in, last-out) 특성에 유의하여 오름차순으로 정렬되어 있는 인접 정점 정보를 역순으로 스택에 넣어야 인접 정점을 오름차순으로 방문할 수 있는 점에 유의하여 구현하고자 하였다. 너비 우선 탐색 알고리즘은 큐(queue) 자료 구조를 활용하여 구현할 수 있는 그래프 순회 알고리즘이다.

 

문제에서 특별한 제한 사항이 없으므로 인접 정점을 오름차순으로 방문하도록 정렬하는 알고리즘, 스택 및 큐 자료 구조는 STL을 활용하였다('algorithm' 헤더의 std::sort, 'stack' 헤더의 std::stack, 'queue' 헤더의 std::queue).

 

구현

DFS와 BFS를 각각 수행하고 난 뒤에 다시 반복문을 돌면서 결과를 출력하는 것이 비효율적이므로, 각각 알고리즘을 수행하면서 자연스럽게 방문 순서대로 정점 번호를 출력하도록 메서드 내에 출력문을 사용하였다. 또한 각각의 알고리즘을 수행하고 나서 정점의 방문 여부를 새로 초기화(반복문 실행 필요)해야 하는 번거로움을 없애기 위해 알고리즘 별로 방문 여부를 나타내는 변수를 따로 만들어 사용하였다(Graph::Vertex::VisitedDFS, Graph::Vertex::VisitedBFS 멤버).

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

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

using namespace std;

struct Graph
{
	struct Vertex
	{
		vector<int> NextIndex;
		bool VisitedByDFS = false;
		bool VisitedByBFS = false;
	};

	Graph(int N)
	{
		V = vector<Vertex>(N);
	}

	void AddEdge(int From, int Dest)
	{
		V[From - 1].NextIndex.push_back(Dest);
	}

	void SortEdge()
	{
		for (Vertex& v : V)
			sort(v.NextIndex.begin(), v.NextIndex.end());
	}

	void DFS(int startIndex)
	{
		printf("%d", startIndex);

		Stack.push(startIndex);
		while (!Stack.empty())
		{
			int index = Stack.top();
			Stack.pop();

			Vertex& vertex = V[index - 1];
			if (!vertex.VisitedByDFS)
			{
				vertex.VisitedByDFS = true;

				if (index != startIndex)
					printf(" %d", index);

				if (!vertex.NextIndex.empty())
				{
					for (size_t i = vertex.NextIndex.size(); i > 0; i--)
						Stack.push(vertex.NextIndex[i - 1]);
				}
			}
		}
		printf("\n");
	}

	void BFS(int startIndex)
	{
		printf("%d", startIndex);

		Queue.push(startIndex);
		while (!Queue.empty())
		{
			int index = Queue.front();
			Queue.pop();

			Vertex& vertex = V[index - 1];
			if (!vertex.VisitedByBFS)
			{
				vertex.VisitedByBFS = true;

				if (index != startIndex)
					printf(" %d", index);

				for (int nextIndex : vertex.NextIndex)
					Queue.push(nextIndex);
			}
		}
		printf("\n");
	}

	vector<Vertex> V;
	queue<int> Queue;
	stack<int> Stack;
};


int main()
{
	int N, M, R;
	scanf("%d %d %d", &N, &M, &R);

	Graph graph = Graph(N);

	int from, dest;
	while (M--)
	{
		scanf("%d %d", &from, &dest);
		graph.AddEdge(from, dest);
		graph.AddEdge(dest, from);
	}

	graph.SortEdge();

	graph.DFS(R);
	graph.BFS(R);

	return 0;
}

 

실행 결과

 

---

 

코드를 통해서도 확인할 수 있지만 DFS의 경우에는 스택 자료 구조에 정렬해놓은 간선 정보를 역순으로 넣는다는 점만 제외하면, 그래프 내 정점들의 순차적인 순회를 위해 보조적으로 사용하는 자료 구조가 스택인지 큐인지에 따라 DFS, BFS 알고리즘으로 나뉠 뿐 전반적인 코드의 구조가 동일하다.