[Algorithm C#] BFS, DFS ( + Back Tracking )

1. BFS(Breadth First Search) - 너비 우선 탐색

최단 경로, 임의의 경로를 찾고 싶을 때, 등에 사용

- 큐(FIFO) 사용

    // 큐를 이용
    public void BFS(int index)
    {
        Node root = nodes[index];
        Queue<Node> queue = new Queue<Node>();
        queue.Enqueue(root);
        root.marked = true;

        while (queue.Count > 0)
        {
            var node = queue.Dequeue();
            for (int i = 0; i < node.adjacent.Count; i++)
            {
                var adjacentNode = node.adjacent[i];
                if (adjacentNode.marked == false)
                {
                    adjacentNode.marked = true;
                    queue.Enqueue(adjacentNode);
                }
            }
            Console.Write(node.data + ",");
        }
    }

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

조합류 최단거리로 갈 수 있는 경로의 수, 목적지 도달 여부, 등에 사용

- 스택(LIFO) 사용, 재귀 함수 사용

    // 스택을 이용
    public void DFS(int index)
    {
        Node root = nodes[index]; ;
        Stack<Node> stack = new Stack<Node>();
        stack.Push(root);
        root.marked = true;

        while (stack.Count > 0)
        {
            var node = stack.Pop();
            for (int i = 0; i < node.adjacent.Count; i++)
            {
                var adjacentNode = node.adjacent[i];
                if (adjacentNode.marked == false)
                {
                    adjacentNode.marked = true;
                    stack.Push(adjacentNode);
                }
            }
            Console.Write(node.data + ", ");
        }
    }

    // 재귀함수를 이용
    public void DFS_Recursive(int index)
    {
        DFS_Recursive(nodes[index]);
    }

    public void DFS_Recursive(Node node)
    {
        node.marked = true;
        Console.Write(node.data + ",");

        for (int i = 0; i < node.adjacent.Count; i++)
        {
            var adjacentNode = node.adjacent[i];
            if (adjacentNode.marked == false)
            {
                dfs_recursive(adjacentNode);
            }
        }
    }

+ Back Tracking ( DFS + 조건 추가 )

DFS 알고리즘에 의해 탐색을 하다가 현재 탐색 중인 노드의 값으로 인해 특정 조건을 만족하지 않게 된다면 해당 노드의 자식 노드들은 더 이상 탐색하지  않고 부모 노드로 돌아가 다음 자식 노드를 탐색하는 것을 말함

즉, 유망한 노드라면 탐색을 이어가고 유망하지 않은 노드라면 탐색하지 않고 다음 자식 노드를 탐색

 

- Stack에 Push하거나 재귀함수를 호출하기 전에 특정 조건을 만족하는지 여부를 판단해 특정 조건을 만족하

지 않는다면 다시 부모노드로 돌아가 다음 자식노드를 체크하도록 로직을 구성하면 됨

 

ex) 백 트래킹 예제 ( CodingTest ) // DFS + 백트래킹 조건 체크 메서드

https://godgjwnsgur7.tistory.com/151

[프로그래머스 C#] Lv.2 N-Queen