[알고리즘] 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

[ 깊이 우선 탐색 | DFS(Depth-First Search) ]

루트 노드(또는 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식

-> 최대한 깊이 내련 후, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동

깊이 우선 탐색(DFS) 탐색 순서

[ 특징 ]

모든 노드를 방문해야 하는 경우 사용.

깊이 우선 탐색(DFS)가 너비 우선 탐색(BFS)보다 조금 더 간단

검색 속도 자체는 너비 우선 탐색(BFS)에 비해 느림

스택(stack) 또는 재귀함수로 구현

 

[ 코드 ]

public class Node {

    public string Name { get; set; }
    public List<Node> Children { get; set; }
    public bool Visited { get; set; }

    public Node(string name) {
        Name = name;
        Children = new List<Node>();
        Visited = false;
    }
}

public void DFS(Node root) {
    if (root == null) {
        return;
    }

    // 방문한 노드는 true
    root.Visited = true;

    // root 노드의 자식 노드를 재귀적으로 탐색
    foreach (Node child in root.Children) {
        DFS(child);
    }
}

 

[ 너비 우선 탐색 | BFS(Breadth-First Search) ]

루트 노드(또는 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

-> 시작 노드로부터 가까운 노드를 먼저 방문하고 멀리 떨어져 있는 노드를 나중에 탐색하는 방식

 

너비 우선 탐색(BFS) 탐색 순서

[ 특징 ]

주로 두 노드 사이의 최단 경로를 찾을 때 사용

큐(Queue)를 이용해 구현

 

[ 코드 ]

public class Node {

    public string Name { get; set; }
    public List<Node> Children { get; set; }
    public bool Visited { get; set; }

    public Node(string name) {
        Name = name;
        Children = new List<Node>();
        Visited = false;
    }
}


public int BFS(Node start, Node end) {
    // 방문한 노드 리스트
    List<Node> visited = new List<Node>();

    // 방문한 노드와 거리 dictionary
    Dictionary<Node, int> distance = new Dictionary<Node, int>();

    // 시작 노드를 방문한 것으로 표시하고 거리를 0으로 설정
    visited.Add(start);
    distance.Add(start, 0);

    // 큐를 생성하고, 시작 노드를 큐에 삽입
    Queue<Node> queue = new Queue<Node>();
    queue.Enqueue(start);

    while (!queue.IsEmpty) {
        // 큐의 첫 번째 노드를 꺼냄
        Node cur = queue.Dequeue();

        // 꺼낸 노드가 종료 노드면 거리를 반환
        if (cur == end) {
            return distance[cur];
        }

        foreach (Node child in cur.Children) {
            if (!visited.Contains(child)) {
            // 만약 꺼낸 노드의 자식 노드를 visited에 없다면 추가
                visited.Add(child);
                //거리를 1 더하고 큐에 삽입
                distance.Add(child, distance[cur] + 1);
                queue.Enqueue(child);
            }
        }
    }

    // 목표 노드에 가지 못하면 -1 반환
    return -1;
}

 

[ DFS, BFS를 활용한 문제 ]

1. 최단 거리를 구하는 문제: BFS

2. 모든 노드를 방문하는 것이 목표인 문제: DFS, BFS

3. 경로의 특징을 저장해야 하는 문제: DFS

-> BFS는 경로의 특징을 저장하지 못 함