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

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[]>[] map = new List<int[]>[n + 1];
    for (int i = 0; i < n; i++)
    {
        int[] inputs = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
        int s = inputs[0];
        map[s] = new List<int[]>();
        for (int j = 1; j < inputs.Length - 1; j += 2)
        {
            int e = inputs[j];
            int d = inputs[j + 1];
            map[s].Add(new int[] { e, d });
        }
    }
    int startPoint = 1;
    bfs(startPoint);
    sw.WriteLine(bfs(startPoint));

    int bfs(int start)
    {
        int result = 0;
        bool[] chk = new bool[n + 1];
        Queue<int[]> queue = new Queue<int[]>();
        queue.Enqueue(new int[] { start, 0 });
        chk[start] = true;
        while (queue.Count > 0)
        {
            int[] cur = queue.Dequeue();
            foreach (int[] next in map[cur[0]])
            {
                if (chk[next[0]]) continue;
                chk[next[0]] = true;
                int nd = cur[1] + next[1];
                if (nd > result)
                {
                    result = nd;
                    startPoint = next[0];
                }
                queue.Enqueue(new int[] { next[0], nd });
            }
        }
        return result;
    }
}

3. 정리

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

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

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

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