C# - DFS(깊이우선탐색)개념 및 코드 구현

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

특정 노드에서 시작하여 그래프를 탐색하면서 제일 깊은 곳으로 들어갔다가 더 이상 들어갈 곳이 없게 되면 다시 돌아와 다른 경로로 탐색을 진행한다. 이를 통해 모든 노드를 방문하고자 할때 사용할 수 있는 탐색 알고리즘이다.

1. 행렬

01 그래프 행렬로 표현

int[,] adj = new int[10, 10]
{
    {0,1,0,0,0,0,0,1,0,0 },
    {1,0,1,0,1,0,0,0,0,0 },
    {0,1,0,1,0,0,0,0,0,0 },
    {0,0,1,0,0,0,0,0,0,0 },
    {0,1,0,0,0,1,1,1,0,0 },
    {0,0,0,0,1,0,0,0,0,0 },
    {0,0,0,0,1,0,0,0,0,0 },
    {1,0,0,0,1,0,0,0,1,0 },
    {0,0,0,0,0,0,0,1,0,1 },
    {0,0,0,0,0,0,0,0,1,0 },
};

---

02 노드의 방문 상태 기록

bool[] visited = new bool[10];

---

03 DFS 알고리즘 구현

public void DFS(int now)
{
    Console.WriteLine(now);
    visited[now] = true;  

    for(int next = 0; next < 10; next++)
    {
        if (adj[now, next] == 0)
            continue;
        if (visited[next]) 
            continue;
        DFS(next);
    }
}

주요 단계 설명

1) 현재 방문한 노드 출력 및 visited에 표시

Console.WriteLine(now);
visited[now] = true;

2) 현재 노드 now와 연결된 모든 노드에대한 반복문

for(int next = 0; next < 10; next++)
{
   
}

3) 현재 노드 now와 다음 노드 next사이에 연결 여부를 확인한다.

만약 값이 0이면 연결이 없으므로 다음 노드로 이동한다.

if (adj[now, next] == 0)
    continue;

4) 방문하였는지 여부 확인

만약 이미 방문한 노드라면 다음 노드로 이동

if (visited[next])
    continue;

5) 위의 두 조건을 만족하지 않은 경우 다음 노드 방문

DFS(next);

---

재귀 원리 설명

---

2. 리스트

01 그래프 리스트로 표현

List<int>[] adj2 = new List<int>[]
{
    new List<int>() {1,7},
    new List<int>() {0,2,4},
    new List<int>() {1,3},
    new List<int>() {2},
    new List<int>() {1,5,6},
    new List<int>() {4},
    new List<int>() {4},
    new List<int>() {0,4,8},
    new List<int>() {7,9},
    new List<int>() {8},
};

---

02 DFS 알고리즘 구현

설명은 위와 같음

public void DFS2(int now)
{
    Console.WriteLine(now);
    visited[now] = true;  

    foreach(int next in adj2[now])
    {
        if (visited[next])
            continue;
        DFS2(next);
    }
}

---

3. 모든 노드를 방문하면서 노드간의 연결성 탐색

public void SerachAll()
{
    visited = new bool[10];
    for (int now = 0; now < 10; now++)
        if (visited[now] == false)
        {
            Console.WriteLine(now);
            DFS2(now);
        }
}

7이 이어져있지 않다고 가정하자

01 now가 0일때 0 - 6을 방문하고

---

02 7이 되었을때 7-9를 방문하면서 모두 방문하게 된다.

 

 

 

 

 

 

 

 

참고 :  본 내용은 MMORPG  PART2 강의를 수강하여 작성하였습니다.

https://www.inflearn.com/course/%EC%9C%A0%EB%8B%88%ED%8B%B0-mmorpg-%EA%B0%9C%EB%B0%9C-part2/dashboard