깊이 우선 탐색

깊이 우선 탐색(DFS, Depth-First Search)는
루트에서 시작해서 다음 분기로 넘어가전에 해당 분기를 환벽하게 탐색하는 방법이다

순회방법

시작 정점에서 한 방향으로 갈수 있는 경로가 있는 곳까지 깊이 탐색해가다가 더이상 갈 곳이 없으면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와 다른 방향의 간선으로 탐색을 하여 계속 반복하여 결국 모든 정점을 방문하게된다


그림을 보면 A-B-C까지 깊게 들어간후 탐색할것이 없으면 다시 돌아가 D를 탐색 같은방식으로 E-F-G까지 탐색하게 된다

문제 풀어보기(바이러스)

원래는 보통 내가 하는 방식으로 class 로 DFS 를 제작하여서 설명할까했는데 DFS 나 BFS 같은경우는 코테같은곳에서 많이 나오는것으로 알고있어 클래스로 구현하는것보다 문제를 풀어보면서 DFS를 이해하는것이 더 좋을것 같다고 생각해서 백준에서 문제를 하나 가져와 DFS를 구현을 해보았다
백준 2606 번 바이러스라는 문제이다

DFS 에서는 해당 노드를 방문해스는지를 확인하기 위한 bool형이 하나 존재 해줄 필요가있다 그 이유가 해당 문제같은경우는 무방향 그래프이다 보니
무한 탐색이 걸릴 수 있기에 bool형을 사용하여 방문을 한 노드를 다시 방문하지 않도록 만든다

#include "bits/stdc++.h"
using namespace std;
#define SIZE 101
int n, m, a, b;
int cnt = 0;
vector<int>vec[SIZE]; //인접 리스트
bool visited[SIZE] = { false, }; //방문했으면 true 
void DFS(int x) //탐색 
{
	if (visited[x])return;
	visited[x] = true;
	cnt++;
	for (int next : vec[x])
	{
		if (visited[next])continue;
		DFS(next);
	}
}
void Insert()
{
	cin >> n;
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> a >> b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}

	DFS(1);
	cout << cnt-1 << '\n';
}
int main()
{
	Insert();
	return 0;
}

현재 그래프는 위 그림처럼 구성이 된다

그리고 1번 컴퓨터에는 바이러스가 걸렸다 정점 1에서 DFS 를 통해 인접되어있는 컴퓨터들을 전부 바이러스로 감염을 시켜준다

1번컴퓨터에서 2번컴퓨터로 2번컴퓨터에서 3번컴퓨터로 , 3번컴퓨터와 인접한 컴퓨터는 2번 뿐이지만 2번컴퓨터는 이미 방문하였으니 for문에서 continue를 진행하고 다시 2번컴퓨터로 돌아온후 5번컴퓨터로 5번에서 6번으로 가게되어 총 4개의 컴퓨터가 1번컴퓨터로 감염이 되게된다
(4번과 7번은 1번과 연결되어있지 않기에 감염이 되지않는다)

시간복잡도

DFS는 그래프의 모든 간선을 조회한다
인접리스트로 구성된 그래프의 DFS O(N+E)
인접행렬로 구성된 그래프의 DFS O(N^2)
N은 정점의 수 E는 간선의 수로
비교적은 적은 간선을 가지고 있는경우는 인접리스트로 그래프를 제작하여 시간복잡도에 유리함을 가져갈수가있다