[백준] 1967 - 트리의 지름

1. 문제

1967번: 트리의 지름

2. 개요

트리의 노드의 개수와 부모, 자식, 비용이 주어진다.

이 때 트리의 지름을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

트리의 지름이란, 트리에 존재하는 모든 경로들 중 가장 긴 경로의 길이이다.

이를 구하기 위해서는

임의의 정점에서 가장 먼 정점을 찾은 뒤, 다시 그 정점에서 가장 먼 정점까지의 거리를 구하면 된다.

즉, dfs 2회로 풀 수 있다.

3-2. Python

import sys

sys.setrecursionlimit(100000000)

def dfs(i = 1, c = 0):
    global maxcostV
    global maxcost

    visited[i] = 1
    for next in graph[i]:
        if visited[next[0]] == 0:
            visited[next[0]] = 1
            dfs(next[0], c + next[1])

    if maxcost < c:
        maxcost = c
        maxcostV = i

n = int(sys.stdin.readline())

graph = [[] for _ in range(n+1)]
visited = [0 for _ in range(n+1)]

for _ in range(n-1):
    parent, child, cost = map(int, sys.stdin.readline().split())

    graph[parent].append([child, cost])
    graph[child].append([parent, cost])

maxcostV = 1
maxcost = 0

dfs()
visited = [0 for _ in range(n+1)]
dfs(maxcostV)

print(maxcost)

3-3. C#

internal class Program
{
    static int[] _visited;
    static List<List<int[]>> _graph;
    static int _maxcost;
    static int _maxcostV;

    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());

        _graph = new List<List<int[]>>();

        for (int i = 0; i <= n; i++)
        {
            _graph.Add(new List<int[]>());
        }

        for (int i = 0; i < n - 1; i++)
        {
            string[] input = Console.ReadLine().Split();
            int parent = int.Parse(input[0]);
            int child = int.Parse(input[1]);
            int cost = int.Parse(input[2]);

            _graph[parent].Add(new int[] { child, cost } );
            _graph[child].Add(new int[] { parent, cost } );
        }

        _maxcost = 0;
        _maxcostV = 1;

        _visited = new int[n + 1];
        dfs(1, 0);
        Array.Fill(_visited, 0);
        dfs(_maxcostV, 0);

        Console.WriteLine(_maxcost);
    }

    static void dfs(int vertex, int cost)
    {
        _visited[vertex] = 1;

        foreach (int[] next in _graph[vertex])
        {
            if (_visited[next[0]] == 0)
            {
                _visited[next[0]] = 1;
                dfs(next[0], cost + next[1]);
            }
        }

        if (_maxcost < cost)
        {
            _maxcost = cost;
            _maxcostV = vertex;
        }
    }
}