[BOJ] 1260번: DFS와 BFS

문제 풀러 가기 링크!

1260번: DFS와 BFS

DFS와 BFS를 실제로 구현해 볼 수 있는 아주 좋은 문제이다.

DFS는 깊이 우선 탐색이여서 최대한 한 정점에서 최대한 깊게 갔다가 다시 돌아오는 작업을 반복해서 모든 정점을 탐색하는 것이고

BFS는 너비 우선 탐색이여서 층 별로 있는 모든 정점을 다 돌면서 내려간다고 보면 된다.

아직 내가 직접 쓴 글이 없어서 개인적으로 정말 좋다고 생각하는 블로그의 글의 링크를 걸어 놓을테니 이 쪽에 가서 자세히 공부하면 된다.

DFS 설명, BFS 설명

개인적으로 DFS는 재귀함수를 이용하는 것을 좋아해서 원래는 스택을 쓰지만 나는 재귀함수로 구현했고 BFS는 스택을 이용해서 구현했다. BFS는 분리하지 않고 main함수에 적어서 가독성이 떨어질텐데... 그 점은 양해 바랍니다 ㅠ

** 아주 중요한 부분인데 문제에서 "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문" 이라고 제시를 했기 때문에 정렬을 시키고 DFS와 BFS를 돌려야 한다. 하지만 테스트 케이스의 문제인지 내가 처음에 제출했을 때 정렬을 하지 않고 냈지만 맞았다.

코드

	#include <cstdio>
	#include <vector>
	#include <queue>
	#include <algorithm>
	using namespace std;
	vector<int> v[1001];
	bool visited[1001];
	int vertex, edge, start;
	void dfs(int now, bool *visited)
	{
	printf("%d ", now);
	visited[now] = true;
	for (int i = 0; i < v[now].size(); i++)
	if (!visited[v[now][i]])
	dfs(v[now][i], visited);
	}
	int main()
	{
	scanf("%d %d %d", &vertex, &edge, &start);
	for (int i = 0, f, t; i < edge; i++) {
	scanf("%d %d", &f, &t);
	v[f].push_back(t);
	v[t].push_back(f);
	}
	// 오름차순 정렬
	for (int i = 1; i <= vertex; i++)
	sort(v[i].begin(), v[i].end());
	dfs(start, visited);
	for(int i = 1; i <= vertex; i++)
	if(!visited[i])
	dfs(i, visited);
	printf("\n");
	fill(visited, visited + vertex + 1, 0);
	// BFS 시작
	queue<int> q;
	q.push(start);
	printf("%d ", start);
	visited[start] = true;
	while(!q.empty())
	{
	int now = q.front();
	q.pop();
	for(int i = 0; i < v[now].size(); i++) {
	int next = v[now][i];
	if(!visited[next])
	{
	q.push(next);
	printf("%d ", next);
	visited[next] = true;
	}
	}
	}
	return 0;
	}

view raw 1260.cpp hosted with ❤ by GitHub