BFS와 DFS

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

• BFS : 주변에 있는 노드를 탐색하며 탐색 범위 확장 (queue활용해서 구현)
• 루트노드부터 주변노드까지 쭉 탐색후 더 깊숙히 탐색
• 예시)자동사냥 : 가장 가까운 적 공격, 추적반경 계산에 사용

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

• 루트노드부터 시작하여 한쪽 방향을 다 본다음에 다른방향 탐색
• Stack혹은 재귀 사용하여 구현 가능
• 예시) 미로 찾기, 모든 경우의 수 찾기

3. BFS와 DFS의 차이 표

4. 코드 구현

동영상 강좌 참조

public class Node<T>
{
    //노드는 자신의값과 다른 노드의 주소를 가지고있다
    public T Value { get; set; } //값
    public List<Node<T>> Neighbors { get; private set; } //여러 노드 기억

    public Node(T value)
    {
        Neighbors = new List<Node<T>>(); //객체 활성화
        Value = value;
    }
}

public class SimpleGraph<T>
{
    List<Node<T>> nodes = new List<Node<T>>(); //그래프가 관리중인 모든 노드 저장

    //▼노드 추가 메서드, 추가하고 만든거 반환
    public Node<T> AddNode(T value)
    {
        Node<T> node = new Node<T>(value);
        nodes.Add(node);
        return node;
    }
    //▼단방향 간선(엣지) 추가  [방향이 있는]
    public void AddEdge(Node<T> from, Node<T> to) //출발,목적지,걸리는 비용
    {
        from.Neighbors.Add(to);
    }
    //▼양방향 간선 추가
    public void AddUndirectedEdge(Node<T> a, Node<T> b)
    {
        a.Neighbors.Add(b);
        b.Neighbors.Add(a);
    }
    //▼그래프 출력
    public void PrintGraph()
    {
        foreach (var node in nodes)
        {
            Console.Write($"{node.Value} -> "); //노드에 있는 값 출력
            foreach (var edge in node.Neighbors) //그 노드 이웃목록 전부 확인
            {
                Console.Write($"{edge.Value} ");
            }
            Console.WriteLine(); //한줄 띄우기
        }
    }

    //BFS (너비우선탐색) 구현 
    //시작노드를 큐에넣고 탐색 시작, 방문노드 기록하여 중복탐색 방지
    //목표노드를 찾으면 탐색종료 및 반환
    //가중치 주면서 BFS는 주석처리했음. 하고싶으면 수정 필요
    
    public void BFS(Node<T> start, Node<T> target)
    {
        Queue<Node<T>> queue = new Queue<Node<T>>(); //임시 큐 만들기
        List<Node<T>> visited = new List<Node<T>>(); //방문 기록을 List로 관리

        queue.Enqueue(start); //천호 넣었다고 가정
        while(queue.Count > 0)
        {
            Node<T> current = queue.Dequeue(); //천호가 담김

            if(visited.Contains(current))
            {
                continue; //방문했으면 패스
            }
            Console.WriteLine($"지하철역 방문: {current.Value}");
            visited.Add(current); //방문했다고 기록
            
            if(current.Equals(target))
            {
                Console.WriteLine($"목표 역{target.Value} 발견!");
                return;
            }
            foreach(var neighbor in current.Neighbors)
            {
                if(visited.Contains(neighbor)== false) //이미 방문한 노드는 큐에 넣지 않음
                {
                    queue.Enqueue(neighbor);
                }
            }
        }
        Console.WriteLine("경로 탐색 실패");
    }
    //DFS -> BFS에서 특정부분만 바꾸면 됨
    //Stack을 통해 구현, 시작을 Stack에 넣고 탐색 시작, 방문노드 기록 중복방지
    //목표 노드 찾으면 탐색종료, 사실 출력
    public void DFS(Node<T> start, Node<T> target)
    {
        Stack<Node<T>> stack = new Stack<Node<T>>(); //임시 스택 만들기
        List<Node<T>> visited = new List<Node<T>>(); //방문 기록을 List로 관리

        stack.Push(start); //천호 넣었다고 가정
        while (stack.Count > 0)
        {
            Node<T> current = stack.Pop(); //천호가 담김

            if (visited.Contains(current))
            {
                continue; //방문했으면 패스
            }
            Console.WriteLine($"지하철역 방문: {current.Value}");
            visited.Add(current); //방문했다고 기록

            if (current.Equals(target))
            {
                Console.WriteLine($"목표 역{target.Value} 발견!");
                return;
            }
            foreach (var neighbor in current.Neighbors)
            {
                if (visited.Contains(neighbor) == false) //이미 방문한 노드는 큐에 넣지 않음
                {
                    stack.Push(neighbor);
                }
            }
        }
        Console.WriteLine("경로 탐색 실패");
    }
    

}
class Program
{
    static void Main(string[] args)
    {
        SimpleGraph<string> subway = new SimpleGraph<string>();
        //▼Node 생성
        var Gwangnaru = subway.AddNode("광나루");
        var CheonHo = subway.AddNode("천호역");
        var GangDong = subway.AddNode("강동역");
        var GilDong = subway.AddNode("길동");
        var DunChonDong = subway.AddNode("둔촌동");
        var OlympicPark = subway.AddNode("올림픽공원역");
        //▼간선(edge)추가
        subway.AddUndirectedEdge(CheonHo, GangDong);
        subway.AddUndirectedEdge(GangDong, DunChonDong);
        subway.AddUndirectedEdge(GangDong, GilDong);
        subway.AddUndirectedEdge(DunChonDong, OlympicPark);
        subway.AddUndirectedEdge(CheonHo, Gwangnaru);
        subway.PrintGraph();
        //▼탐색(BFS와 DFS)
        subway.BFS(CheonHo, OlympicPark);
        subway.DFS(CheonHo, OlympicPark);
    }
}

5. 코드 구현 (가중치 추가) -> 추가예정