백준# 1967 - 트리의 지름

 

https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

이번 문제는 트리로 분류된 1967번 트리의 지름 입니다.

(글이 늦었습니다... 아시때문에 정신이 없어서... 이제 제 방이 와이파이존이 됐으니 열심히 쓰겠습니다!!) 

 

 

문제를 보면 복잡해 보이지만 그렇지 않습니다.

트리를 처음 하신다면 이 두가지를 기억해 주세요.

 

1. 트리의 기본은 재귀로 돌리는 것이다.

2. 트리를 어떻게 구성할 것인가 (C++ 이라면 포인터 배열, C#이나 JAVA 라면 배열이나 리스트 등)

 

using System;
using System.Collections.Generic;
using System.Linq;
 
namespace _1967
{
    class Program
    {
        public class Node
        {
            public static int MaxDistance;
 
            public int nodeNum;
            public int weight;
            public int distance;
            public List<Node> children;
 
            public Node(int nodeNum, int weight)
            {
                this.nodeNum = nodeNum;
                this.weight = weight;
                this.children = new List<Node>();
            }
 
            public void Insert(Node node)
            {
                this.children.Add(node);
            }
 
            public void SetTreeDistance()
            {
                if (this.children.Count == 0)
                    this.distance = 0;
 
                else if(this.children.Count == 1)
                {
                    this.children[0].SetTreeDistance();
 
                    this.distance = this.children[0].distance + this.children[0].weight;
                    if (this.distance >= Node.MaxDistance)
                        Node.MaxDistance = this.distance;
                }
 
                else
                {
                    this.children.ForEach(x => x.SetTreeDistance());
 
                    var ordered = this.children.OrderByDescending(x => x.distance + x.weight)
                        .ToList();
 
                    if (ordered[0].distance + ordered[1].distance
                        + ordered[0].weight + ordered[1].weight > Node.MaxDistance)
                        Node.MaxDistance = ordered[0].distance + ordered[1].distance
                        + ordered[0].weight + ordered[1].weight;
 
                    this.distance = ordered[0].distance + ordered[0].weight;
                }
            }
 
        }
 
 
        static void Main(string[] args)
        {
            int count = int.Parse(Console.ReadLine()) - 1;
            Node.MaxDistance = 0;
            Queue<Node> nodeQueue = new Queue<Node>();
 
            Node tree = new Node(1, 0);
            nodeQueue.Enqueue(tree);
 
            for(int i = 0; i < count; i++)
            {
                var input = Console.ReadLine().Split(' ').ToList()
                    .Select(x => int.Parse(x)).ToList();
                var node = new Node(input[1], input[2]);
                nodeQueue.Enqueue(node);
 
                while (nodeQueue.Peek().nodeNum != input[0])
                    nodeQueue.Dequeue();
 
                nodeQueue.Peek().Insert(node);
            }
 
            tree.SetTreeDistance();
            Console.Write(Node.MaxDistance);
        }
    }
}
 

소스 코드 입니다.

 

보면 각 노드(원형의 점)에 번호가 붙어있고 엣지(선)에 가중치가 붙어있습니다.

노드와 가중치를 따로 놓기도 하지만 이번 문제는 그럴 필요는 없습니다.

 

각 노드에 weight, distance, children을 가지게 했습니다.

weight : 노드에서 노드로 넘어가는 가중치.

distance : 자기 자식들의 distance 중 가장 큰 distance

children : 자기 자식으로 달리는 노드들.

 

 

메인 함수에서 입력을 받고 그것을 큐에 집어넣었습니다.

문제 입력의 특성 상 최상위 노드부터 자식이 달리기 때문에 큐에 넣어놓으면

앞에서 부터 달아주고 부모가 아니라면 버리면 될 것입니다.

 

문제의 핵심은 SetTreeDistance() 되겠습니다.

1. 자식이 없다면 distance는 나올 수 없습니다.

2. 자식의 수가 1이라면 distance는 자기 자식의 distance + 그 자식으로 가는 weight 되겠습니다.

3. 자식의 수가 여럿이라면 자기 자식들의 distance 중 가장 큰 2명만 가져와

그 둘의 weight 을 더하면 자기의 distance가 되겠습니다.

 

즉 distance는 문제에서 찾고자 하는 답이고 그 답을 모든 노드가 한 번씩 구해봐야

가장 큰 distance가 무엇인지 알 수 있습니다.

 

distance를 구할 때마다 최대 distance를 트리 static 변수에 업데이트 하고

마지막으로 그 결과를 출력 했습니다.