[알고리즘 문제 풀기] 트리의 지름(1967)

1. 문제 풀이 아이디어

• 트리를 인접 리스트로 표현하고, BFS를 두 번 수행하여 끝과 끝을 구하는 방식으로 문제를 해결할 수 있다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int n = int.Parse(sr.ReadLine());
    List<int[]>[] list = new List<int[]>[n + 1];
    for (int i = 1; i <= n; i++) list[i] = new List<int[]>();
    for (int i = 1; i < n; i++)
    {
        int[] inputs = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
        list[inputs[0]].Add(new int[] { inputs[1], inputs[2] });
        list[inputs[1]].Add(new int[] { inputs[0], inputs[2] });
    }
    int far = 1;
    bfs();
    sw.WriteLine(bfs());
    int bfs()
    {
        int max = 0;
        bool[] chk = new bool[n + 1];
        Queue<int[]> que = new Queue<int[]>();
        que.Enqueue(new int[] { far, 0 });
        chk[far] = true;
        while (que.Count > 0)
        {
            int[] cur = que.Dequeue();
            foreach (int[] i in list[cur[0]])
            {
                if (chk[i[0]]) continue;
                chk[i[0]] = true;
                int dist = cur[1] + i[1];
                if (dist > max)
                {
                    max = dist;
                    far = i[0];
                }
                que.Enqueue(new int[] { i[0], dist });
            }
        }
        return max;
    }
}

3. 정리

• list[i]에 i번 노드와 연결된 노드와 거리 정보를 저장한다.

• 첫 번째 BFS를 수행하여 임의의 노드에서 가장 먼 노드를 찾는다.

• 두 번째 BFS를 수행하여 첫 번째 BFS에서 찾은 노드에서 가장 먼 거리를 구한다.

• 두 번의 BFS를 통해 트리의 지름을 구한다.