[백준] 1260번 DFS와 BFS

 

 

 

 

 

문제

 

소스코드

#include<iostream>
#include<queue>                  
const int MAX_VERTEX = 1001;
const int MAX_EDGE = 10001;
class cmp;
std::priority_queue<int, std::vector<int>, cmp>* bfs_q;
std::priority_queue<int, std::vector<int>, cmp>* dfs_q;

bool bfs_visited[MAX_VERTEX];
bool dfs_visited[MAX_VERTEX];


class cmp {
public:
	bool operator()(int lhs, int rhs) {
		return lhs > rhs;
	}
};

//using recursive call
void DFS(int started) {

	auto iter = dfs_q[started];
	if (dfs_visited[started] == false) {
		dfs_visited[started] = true;
		std::cout << started << " ";
	}

	while (!iter.empty()) {
		int i = iter.top();
		iter.pop();
		if (dfs_visited[i] == false) {
			DFS(i);
		}
	}
	return;
}

//using Queue
void BFS(int started) {
	std::queue<int> q;
	q.push(started);
	bfs_visited[started] = true;
	std::cout << started << " ";
	while (!q.empty()) {
		auto iter = bfs_q[q.front()];
		q.pop();

		while (!iter.empty()) {
			int i = iter.top();
			iter.pop();
			if (bfs_visited[i] == false) {
				bfs_visited[i] = true;
				q.push(i);
				std::cout << i << " ";
			}
		}

	}
}

int main() {

	int vertex = 0;
	int edge = 0;
	int started = 0;
	std::cin >> vertex >> edge >> started;

	bfs_q = new std::priority_queue<int, std::vector<int>, cmp>[vertex + 1];
	dfs_q = new std::priority_queue<int, std::vector<int>, cmp>[vertex + 1];

	for (int i = 0; i < MAX_VERTEX; ++i) {
		bfs_visited[i] = false;
		dfs_visited[i] = false;
	}

	for (int i = 0; i < edge; ++i) {
		int from_v, to_v;
		std::cin >> from_v >> to_v;

		bfs_q[from_v].push(std::move(to_v));
		dfs_q[from_v].push(std::move(to_v));

		bfs_q[to_v].push(std::move(from_v));
		dfs_q[to_v].push(std::move(from_v));
	}
	DFS(started);
	std::cout << "\n";
	BFS(started);

}

 

 

후기

깊이 우선 탐색(Depth First Search)와너비 우선 탐색(Breadth First Search)을 알고 있다면 그렇게 어려운 문제는 아니다. 기존 탐색 방법과 차이가 있다면 더 정점 번호가 작은 것을 우선 탐색한다는 것 인대 Sort를 하는 방법도 있고 여러 방법이 있겠지만(다른 사람들이 푼 코드를 몇 개 보니 대부분 Vector에 Sort를 사용하였다.) 나는 우선순위 큐(Priority Queue) 라이브러리를 사용해서 구현을 하였다.  다른 의미로 멍청한 짓을 한 문제였는데 틀렸다는 결과를 보고 여러 반례를 찾거나 만들었지만 정답이 틀리지 않아서 고생 좀 하다가 배열의 크기를 1001이 아닌 1000으로 해서 계속 틀린 문제였다. 

 

 

출처 및 레퍼런스

문제 링크:https://www.acmicpc.net/problem/1260