백준 1260: DFS와 BFS

문제 요약

정점과 간선, 탐색 시작 정점이 주어지면, 해당 정점으로부터 DFS 및 BFS한 결과를 각 줄마다 차례로 출력하면 된다.

문제 분류

• 그래프 이론
• 그래프 탐색
• DFS
• BFS

문제 풀이

한 쌍으로 주어지는 간선을 표현하는 방법에 대해, pair객체를 vector의 원소로 두는 방법, 그리고 multimap을 사용하는 방법이 있다.

vector와 multimap의 시간복잡도를 비교해보면 vector의 정렬에 O(nlogn)만큼 걸리고, 원소 탐색에 O(n)이라고 생각할 수 있다.

mulitmap을 이용할 경우 삽입과 동시에 정렬되므로 삽입에 O(logn), 탐색에 O(logn)정도로 multimap이 훨씬 효율적인 방법이라고 할 수 있겠다.

이전에 vector로 풀었던 적이 있어서, multimap 으로 다시 풀어보았다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;

multimap<int, int> g;
bool visited[1001];

void dfs(int n)
{
	vector<int> v;
	printf("%d ", n);
	auto rg = g.equal_range(n);
	for (auto& it = rg.first; it != rg.second; it++) {
		v.push_back(it->second);
	}
	sort(v.begin(), v.end());
	for (auto it : v) {
		if (!visited[it]) {
			visited[it] = true;
			dfs(it);
		}
	}
}

int main()
{
	int in, in2, n, m, v;
	queue<int> q;
	vector<int> vv;
	cin >> n >> m >> v;
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d", &in, &in2);
		g.insert({ in,in2 });
		g.insert({ in2,in });
	}
	visited[v] = true;
	dfs(v);
	fill(visited, visited + n + 1, false);
	visited[v] = true;
	printf("\n");
	q.push(v);
	while(!q.empty()) {
		vv.clear();
		auto t = q.front();
		printf("%d ", t);
		q.pop();
		auto rg = g.equal_range(t);
		for (auto& it = rg.first; it != rg.second; it++) {
			if (!visited[it->second]) {
				visited[it->second] = true;
				vv.push_back(it->second);
			}
		}
		sort(vv.begin(), vv.end());
		for (auto it : vv)
			q.push(it);
	}
}