DFS

DFS ( Depth First Search)

Depth-First-Search 이름에서 부터 탐색기법이라는 것을 알 수 있는데
대표적인 그래프 탐색 알고리즘 중 하나이다.

그래프에서 깊이 우선적으로 탐색하는 알고리즘으로 간단히 말해서 한쪽 방향으로 탐색을 끝낸 후 다시 탐색 안한 부분으로 올라와서 또 한쪽 방향으로 쭉 탐색 한다고 생각하면 된다.

---

위에 그래프에서 보면 탐색 순서는 0 - 1 - 2 - 3 - 4 - 5가 될 것이다.

그래서 그래프를 2차원 배열로 만들어보면,
연결되지 않으면 0
연결되어 있으면 1

class Graph
{
	int[,] adj = new int[6,6]
    {
    	{ 0, 1, 0, 1, 0, 0 },
        { 1, 0, 1, 1, 0, 0 },
        { 0, 1, 0, 0, 0, 0 },
        { 1, 1, 0, 0, 1, 0 },
        { 0, 0, 0, 1, 0, 1 },
        { 0, 0, 0, 0, 1, 0 },
    }
}

그래프를 만들었으면, DFS 를 만들어야 하는데
1. 방문을 한지 안한지 Check
2. 시작점을 지정
3. 시작점과 연결된 정점들을 하나씩 확인하여 방문하지 않은 곳을 방문

bool[] visited = new bool[6];
public void DFS(int now)
{
	//현재 방문 노드 출력 후 방문표시
	Console.WriteLine(now);
	visited[now] = true;
    for(int next =0; next < adj.GetLength(0); next++)
    {
    	if(adj[now,next] == 0) //연결되어 있지않으면 스킵
        	continue;
        if(visited[next]) //방문한곳이면 스킵
        	continue;
        DFS(next); //재귀 함수
    }
}

재귀 함수를 이해하기 힘들면 천천히 하나씩 생각해보면 된다.
DFS(0)이라 하면 0번부터 탐색한다
1. 0 출력 후 visited[0] =true
2. for문에서 next=0일때 adj[0,0] ==0 이니 스킵
3. next=1일때 adj[0,1] ==1 이고 visited[1]이 false이니 재귀함수 DFS(1)
4. 1 출력 후 visited[1] = true
5.반복
그래서 모든 연결된 그래프를 탐색하고 종료 할 것이다.

---

그래프는 List로도 표현할 수 있다.
각 노드들로부터 연결된 노드를 표시

List<int> adj2 = new List<int>[]
{
	new List<int>() { 1, 3 },     //0번 노드 ( 1번,3번 노드 연결되어있음)
    new List<int>() { 0, 2, 3 }, //1번 노드
    new List<int>() { 1 },       //2번 노드
    new List<int>() { 0, 1, 4 }, //3번 노드
    new List<int>() { 3, 5 },    //4번 노드
    new List<int>() { 4 },      //5번 노드
}

public void DFS2(int now)
{
	Console.WriteLine(now)
    visited[now] = true;
    
    foreach(int next in adj2[now]) //연결되어 있지않으면 스킵
    {
    	if(visited[next]) //이미 방문했으면 스킵
        	continue;
        DFS2(now);
    }
}

DFS2(0)

1. 0 출력 후 visited[0] = true
2. foreach(int next in adj2[0])
3. { 1 , 3} 중에 next = 1 에서 방문하지않았으니까 DFS2(1)
4. 1 출력 후 visited[1] = true
5. foreach(int next in daj2[1])
6. { 0, 2, 3 } 0은 방문했으니까 패스 next = 2 로 DFS(2)
7. 계속 탐색...

---

만약 3번과 4번이 끊겨있다 한다면

public void SearchAll()
{
	visited = new bool[6];
    for(int now = 0; now < 6; now++)
    	if(visited[now] == false)
        	DFS(now);
}

를 한다면 끊겨있어도 모든 노드를 탐색 할 수 있다.

위에 코드를 실행한다면 0,1,2,3 이 visited = true가 되고
그 후 4,5가 visited = true가 될 것이다.