[BOJ][C#] 1967 트리의 지름

📕 문제

📌 링크

📗 접근 방식

• 노드 연결을 기록할 Dictionary 준비
• 노드A 노드B 가중치(W)로 입력을 받았을 때 다음과 같이 딕셔너리에 삽입한다.
  • Key : A, Value : (B, W)
  • Key : B, Value : (A, W)
• 모든 노드를 기준으로 각 노드와 다른 모든 노드들과의 거리를 판단해준다.
  • 다른 노드들과의 거리 계산 중 연결되어 있지 않다면 BFS를 이용해 해당 노드와의 거리를 계속해서 기록해준다.
• 계산한 거리 중 가장 큰 값을 기록한다.

📘 코드

namespace BOJ  
{  
    public class Input<T>  
    {  
        public static T GetInput() => ConvertStringToType(Console.ReadLine());  
        public static T[] GetInputArray() => Array.ConvertAll(Console.ReadLine().Split(), Input<T>.ConvertStringToType);  
        private static T ConvertStringToType(string input) => (T)Convert.ChangeType(input, typeof(T));  
    }  
      
    class No_1967  
    {  
        static void Main()  
        {  
            int nodeCount = Input<int>.GetInput();  
  
            Dictionary<int, List<(int, int)>> graph = new Dictionary<int, List<(int, int)>>();  
  
            for (int i = 0; i < nodeCount; i++)  
            {  
                graph[i] = new List<(int, int)>();  
            }  
  
            for (int i = 0; i < nodeCount - 1; i++)  
            {  
                int[] arr = Input<int>.GetInputArray();  
                int parent = arr[0] - 1;  
                int child = arr[1] - 1;  
                int weight = arr[2];  
  
                graph[parent].Add((child, weight));  
                graph[child].Add((parent, weight));  
            }  
  
            int diameter = FindDiameter(graph, nodeCount);  
            Console.WriteLine(diameter);  
        }  
  
        static int FindDiameter(Dictionary<int, List<(int, int)>> graph, int nodeCount)  
        {  
            int diameter = 0;  
  
            for (int i = 0; i < nodeCount; i++)  
            {  
                int pathLength = GetPathLength(i, graph, nodeCount);  
                diameter = Math.Max(diameter, pathLength);  
            }  
  
            return diameter;  
        }  
  
        static int GetPathLength(int startNode, Dictionary<int, List<(int, int)>> graph, int nodeCount)  
        {  
            int[] distance = new int[nodeCount];  
            bool[] visited = new bool[nodeCount];  
  
            Queue<int> queue = new Queue<int>();  
            queue.Enqueue(startNode);  
            visited[startNode] = true;  
  
            while (queue.Count > 0)  
            {  
                int current = queue.Dequeue();  
  
                foreach ((int neighbor, int weight) in graph[current])  
                {  
                    if (!visited[neighbor])  
                    {  
                        queue.Enqueue(neighbor);  
                        visited[neighbor] = true;  
                        distance[neighbor] = distance[current] + weight;  
                    }  
                }  
            }  
  
            return distance.Max();  
        }  
    }  
}

📙 오답노트

📒 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 트리
• 깊이 우선 탐색