DFS 깊이우선탐색

깊이우선탐색은 그래프의 모든 정점을 탐색하는 알고리즘중 하나

주변의 모든 인접점을 확인하며 탐색을 진행하는 BFS 알고리즘과는 반대로

현재 갈수있는 경로가 있다면 해당경로의 가장 깊은곳까지 탐색하는 방식이다.

 

해당알고리즘은 Stack 자료구조나 재귀함수로 구현하는게 일반적이다.

 

비선형자료구조를 탐색, 사이클 감지에 유용하며

모든 레벨의 노드를 기억해야하는 BFS 알고리즘과는 다르게 DFS 현재의 경로만 기억하면 되므로

BFS 보다는 메모리 효율을 높일수 있다는 점이 있다.

 

또한 DFS 탐색방법과 백트레킹방식으로 최적의 해를 구하는데 유용할수 있다.

 

0 정점을 시작으로 탐색을 진행해보자

0 정점의 인접점은 1 , 2 의 정점이 있다.

재귀함수 형태로 진행되는 과정을 표현해보자면 위의 그림과 같다.

 

함수를 계속 진행하며 더이상 경로가 없게 될때까지의 과정이다. ( 탐색 과정 0 - 1 - 3 - 6 )

DFS(6) 에서 원하는 해를 구하지 못했거나, 더 탐색을 진행해야하는경우 기저조건의 Return으로 다시 되돌아간다.

그럼 다음으로 처리해야 할 함수는 DFS(7) 로 탐색이 진행된다.

 

 

해를 구하게될때까지의 탐색 과정이다.

DFS(6) 에서 더이상의 경로가 없으므로 Return -

DFS(7) 에서 더이상의 경로가 없으므로 Return - 

DFS(3) 에서 더이상의 경로가 없으므로 Return -

DFS(1) 에서 재귀호출된 DFS(4) 탐색 -

DFS(4) 에서 재귀호출로 DFS(8) 탐색완료

 

하나의 길만 끝까지 들어가본다 라는게 이번 알고리즘의 핵심이다.

 

 

 

문제 https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

 

풀이 

using System.Text;

int[] input = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
StringBuilder sb = new StringBuilder();

int vertexes = input[0];
int nodeCount = input[1];
int startNum = input[2];

int[] visited = new int[vertexes+1];
int[][] nodes = new int[vertexes+1][];

for (int i = 0; i < nodeCount; i++)
{
    input = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);

    int a = input[0];
    int b = input[1];

    if(nodes[a] == null)
        nodes[a] = new int[vertexes+1];
    
    if(nodes[b] == null)
        nodes[b] = new int[vertexes+1];

    nodes[a][b] = 1;
    nodes[b][a] = 1;
}

DFS(nodes,visited,startNum);
Array.Fill(visited,0);
sb.AppendLine();
BFS(nodes,visited,startNum);

System.Console.WriteLine(sb);

void DFS(int[][] nodes,int[] visited, int start)
{
    sb.Append($"{start} ");

    if(nodes[start] == null || nodes[start].Sum() == 0)
        return;

    visited[start] = 1;

    for (int i = 1; i < visited.Length; i++)
    {
        if(visited[i] == 1 || nodes[start][i] == 0)
            continue;

        DFS(nodes,visited,i);
    }
}

void BFS(int[][] nodes,int[] visited, int start)
{
    Queue<int> q = new Queue<int>();

    q.Enqueue(start);
    visited[start] = 1;

    while(true)
    {
        if(q.Count <= 0)
            break;

        int info = q.Dequeue();
        sb.Append($"{info} ");

        if(nodes[info] == null)
            continue;

        for (int i = 1; i < nodes[info].Length; i++)
        {
            if(nodes[info][i] == 0 || visited[i] == 1)
                continue;

            q.Enqueue(i);
            visited[i] = 1;
        }
    }
}

 

 

미흡한부분이나 개선될 수 있는부분이 있다면 댓글 부탁드립니다.