C# 알고리즘

오늘 배운 알고리즘 내용을 일부 설명

DFS (깊이 우선 탐색)

DFS란 현재 노드에서 가능한 한 깊이 끝까지 내려간 뒤, 더 이상 갈 곳이 없으면 이전 노드로 되돌아가서 다시 탐색하는 것.

재귀 호출 또는 스택을 사용.

void DFS(int node, bool[] visited, List<int>[] graph) 인접 리스트 (List<int>[] 형태)
{
    visited[node] = true; // 방문 여부 체크
    Console.WriteLine(node);

    foreach (int next in graph[node]) 노드 방문 -> 인접 노드 중 아직 방문 안 한 것 재귀 호출 -> 끝까지 갔다가 다시 돌아옴
    {
        if (!visited[next])
            DFS(next, visited, graph);
    }
}

  
List<int>[] graph = new List<int>[4];
for (int i = 0; i < 4; i++) graph[i] = new List<int>();
graph[0].Add(1);
graph[0].Add(3);
graph[1].Add(0); graph[1].Add(2);
graph[2].Add(1);
graph[3].Add(0);

bool[] visited = new bool[4];
DFS(0, visited, graph);  // 출력: 0 1 2 3

List형태인 graph와 확인 했는지 여부를 확인하기 위한 bool 값을 가질 배열 visited 생성 후 DFS 호출

DFS 내에서 호출될 때 마다 visited에 true를 넣고, foreach를 통해서 visited가 true가 아니면 DFS 재호출하여 확인하도록 함

BFS (너비 우선 탐색)

시작 노드에서 가까운 노드부터 차례대로 방문하여, 각 단계마다 같은 거리에 있는 노드들을 먼저 처리
큐(Queue)를 사용

void BFS(int start, List<int>[] graph)
{
    Queue<int> queue = new Queue<int>();
    bool[] visited = new bool[graph.Length];

    queue.Enqueue(start);
    visited[start] = true;

    while (queue.Count > 0)
    {
        int node = queue.Dequeue();
        Console.WriteLine(node);

        foreach (int next in graph[node])
        {
            if (!visited[next])
            {
                visited[next] = true;
                queue.Enqueue(next);
            }
        }
    }
}

BFS(0, graph);  // 출력: 0 1 3 2

특징

DFS

방식 : 깊이 우선
자료구조 : 재귀(스택)
사용 상황 : 미로 탈출, 백트래킹
메모리 : 깊이 많을수록 메모리 많이 사용

BFS

방식 : 너비 우선
자료구조 : 큐
사용 상황 : 최단 거리 탐색
메모리 : 큐가 커질 수 있음