BaekJoon 1260 DFS와 BFS

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

소스결과 2968 KB 8 ms

출처 Backjoon

언어 C++ 17

 

설명

DFS ( Depth - First - Search ) 깊이 우선 탐색

BFS ( Breadth - First - Search ) 넓이 우선 탐색

 

DFS Page : https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

BFS Page : https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

 

이번 문제에서 보이는 DFS와 BFS 의 차이는

순서 뿐만이 아니라 DFS는 재방문을 함수 스택에 넣을 때 검사 하고 BFS는 queue에서 꺼냈을때 검사한다는 것이다.

BFS는 깊이를 우선순위로 보기 때문에 공통된 자식이 있을 경우 중복된 값을 넣을 수 있다.

queue에 넣을 때 방문한 것으로 판단 하게 하는 방법도 존재하지만 밑의 소스에서는 그 방법을 사용하지 않았다.

 

알고리즘

1. 정점의 수와 간선, 시작지점을 입력받는다.

2. DFS를 수행하며 출력

3. BFS를 수행하며 출력

 

소스코드

#include <iostream>
#include <queue>

using namespace std;

int n;
bool adjMat[1000][1000];
bool dfsCheck[1000];
bool bfsCheck[1000];

void DFS(int pos)
{
	// 방문 확인
	dfsCheck[pos] = true;
	cout << pos + 1 << ' ';

	for (int i = 0; i < n; i++)
	{
		if (adjMat[pos][i] && !dfsCheck[i])
			DFS(i);
	}
}

int main()
{
	int m, start;
	queue<int> q;

	cin >> n >> m >> start;

	for (int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		adjMat[x - 1][y - 1] = adjMat[y - 1][x - 1] = true;
	}
	
	// DFS 실행
	DFS(start-1);

	// DFS BFS 구분
	cout << '\n';

	// BFS
	q.push(start - 1);
	
	while (!q.empty())
	{
		int cur = q.front();
		q.pop();

		// 재 방문시 출력하지 않고 다음 노드 탐색
		if (bfsCheck[cur])
			continue;

		bfsCheck[cur] = true;
		cout << cur + 1 << ' ';

		for (int i = 0; i < n; i++)
		{
			if (adjMat[cur][i])
				q.push(i);
		}
	}

	return 0;
}