[백준] 1167 - 트리의 지름

1. 문제

1167번: 트리의 지름

2. 개요

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

3. 풀이 및 코드

3-1. 풀이

[백준] 1967 - 트리의 지름

1967번 트리의 지름 문제와 똑같은 문제다.

왜 난이도 차이가 이렇게 나는지는 모르겠다..

먼저 임의의 한 점에서 가장 먼 거리의 점을 구한다.

그 다음 다시 이 점에서 가장 먼 거리의 정점까지의 거리가 트리의 지름이 된다.

DFS 두 번으로 풀 수 있는 문제.

3-2. Python

import sys

def DFS(i, c):
    global maxcostV
    global maxcost

    visited[i] = True

    for next in graph[i]:
        if visited[next[0]]:
            continue

        visited[next[0]] = True
        DFS(next[0], c + next[1])

    if maxcost < c:
        maxcost = c
        maxcostV = i

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

graph = [[] for i in range(V+1)]
visited = [False for i in range(V+1)]

for i in range(V):
    info = list(map(int, sys.stdin.readline().split()))

    for j in range(1, len(info), 2):
        if info[j] == -1:
            break

        graph[info[0]].append([info[j], info[j+1]])
        graph[info[j]].append([info[0], info[j+1]])

maxcostV = 1
maxcost = 0

DFS(1, 0)
visited = [False for i in range(V+1)]
DFS(maxcostV, 0)

print(maxcost)

3-3. C#

namespace boj_1167
{
    internal class Program
    {
        static bool[] visited;
        static List<List<int[]>> graph;
        static int maxcost;
        static int maxcostV;

        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int V = int.Parse(sr.ReadLine());

            graph = new List<List<int[]>>();
            visited = new bool[V + 1];

            for (int i = 0; i < V + 1; i++)
                graph.Add(new List<int[]>());

            for (int i = 0; i < V; i++)
            {
                int[] input = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);

                for (int j = 1; j < input.Length; j += 2)
                {
                    if (input[j] == -1)
                        break;

                    graph[input[0]].Add(new int[] { input[j], input[j + 1] });
                    graph[input[j]].Add(new int[] { input[0], input[j + 1] });
                }
            }

            maxcost = 0;
            maxcostV = 1;

            DFS(1, 0);
            Array.Fill(visited, false);
            DFS(maxcostV, 0);

            sw.WriteLine(maxcost);
            sw.Close();
        }

        static void DFS(int i, int c)
        {
            visited[i] = true;

            foreach (int[] next in graph[i])
            {
                if (visited[next[0]])
                    continue;

                visited[next[0]] = true;
                DFS(next[0], c + next[1]);
            }

            if (maxcost < c)
            {
                maxcost = c;
                maxcostV = i;
            }
        }
    }
}