[C#]프로그래머스/가장 먼 노드/BFS,그래프

using System.Linq;
using System.Collections.Generic;
 
public class Solution
{
    public class Node
    {
        public int Value;
        public HashSet<Node> Neighbors;
 
        public Node(int value)
        {
            Value = value;
            Neighbors = new HashSet<Node>();
        }
 
        public void AddNeighbor(Node neighbor)
        {
            Neighbors.Add(neighbor);
        }
    }
 
    public class Graph
    {
        public Dictionary<int, Node> Nodes;
 
        public Graph()
        {
            Nodes = new Dictionary<int, Node>();
        }
 
        public void AddNode(int value)
        {
            if (!Nodes.ContainsKey(value))
                Nodes.Add(value, new Node(value));
        }
 
        public void AddEdge(int fromValue, int toValue)
        {
            Node fromNode = Nodes[fromValue];
            Node toNode = Nodes[toValue];
 
            if (!fromNode.Neighbors.Contains(toNode))
                fromNode.AddNeighbor(toNode);
 
            if (!toNode.Neighbors.Contains(fromNode))
                toNode.AddNeighbor(fromNode);
        }
    }
 
    public int solution(int n, int[,] edge)
    {
        Graph graph = new Graph();
 
        for (int i = 0; i < edge.GetLength(0); i++)
        {
            //노드 추가
            graph.AddNode(edge[i, 0]);
            graph.AddNode(edge[i, 1]);
 
            //간선 연결
            graph.AddEdge(edge[i, 0], edge[i, 1]);
        }
 
        //시작 노드 => value가 1인 노드
        Node StartNode = graph.Nodes[1];
 
        return FindFurthestNodesCount(StartNode);
    }
 
    private int FindFurthestNodesCount(Node startNode)
    {
        //노드별 거리가 담길 Dic
        Dictionary<Node, int> distances = new Dictionary<Node, int>();
        
        //방문 노드를 담을 Hashset
        HashSet<Node> visitedNode = new HashSet<Node>();
 
        //BFS 탐색을 진행할 Queue
        Queue<Node> bfsQueue = new Queue<Node>();
 
        //시작 노드의 거리를 1로 초기화
        distances[startNode] = 1;
        visitedNode.Add(startNode);
        bfsQueue.Enqueue(startNode);
 
        int maxDistance = 0;
 
        while (bfsQueue.Count > 0)
        {
            Node currentNode = bfsQueue.Dequeue();
            int currentDistance = distances[currentNode];
 
            //현재 노드까지의 거리가 최대 거리보다 멀다면, 최대 거리와 가장 먼 노드를 갱신
            if (currentDistance > maxDistance)
                maxDistance = currentDistance;
 
            //현재 노드의 이웃 노드를 검색
            foreach (Node neighbor in currentNode.Neighbors)
            {
                //아직 거리 갱신이 안되어있는 것만 큐에 넣는다.
                if (!visitedNode.Contains(neighbor))
                {
                    //이웃 노드의 거리 = 현재 노드까지의 거리 + 1;
                    distances[neighbor] = currentDistance + 1;
                    visitedNode.Add(neighbor);
                    bfsQueue.Enqueue(neighbor);
                }
            }
        }
 
        //최대거리와 동일한 노드를 묶고 그 개수를 반환.
        return distances.Where(x => x.Value == maxDistance).Count();
    }
}