<Lv.4> 트리 트리오 중간값 (프로그래머스 : C#)

https://school.programmers.co.kr/learn/courses/30/lessons/68937

📕 문제 설명

1. 두 점 사이 거리는 두 점을 잇는 경로 상 간선의 개수
2. f(a,b,c) = 각 점 pair 사이의 거리 중 중간 값 (a,b,c = 임의의 점)

• Input
  트리 정점 개수 n, 트리 간선 정보 edges
• Output
  임의의 3개의 점 뽑아 만들 수 있는 모든 f 중 최대값

예제

풀이

처음 시작 노드를 잡았을 때 해당 노드로부터 가장 거리가 먼 노드를 찾는다. 이때, 가장 거리가 먼 노드가 2개 있으면 해당 거리가 바로 답이 된다. 만약 1개라면 거리 먼 노드 기준 다시 거리 먼 노드를 찾은 후 거기서 두 번째로 멀리 떨어진 길이가 중간값이 된다.

using System;
using System.Collections.Generic;

public class Solution {
    int n;
    public int solution(int nodeCnt, int[,] edges) {
        n = nodeCnt;
        
        List<int>[] graph = new List<int>[n+1];
        for (int i = 1; i <= n; i++)
        {
            graph[i] = new List<int>();
        }
        for (int i = 0; i < edges.GetLength(0); i++)
        {
            int departNode = edges[i, 0];
            int arrivalNode = edges[i, 1];
            
            graph[departNode].Add(arrivalNode);
            graph[arrivalNode].Add(departNode);
        }
        // 루트에서 가장 먼 노드 거리 (leaf node)
        List<(int, int)> farFromRoot = BFS(graph, 1);
        // leaf node에서 가장 먼 노드 거리
        List<(int, int)> farFromLeaf = BFS(graph, farFromRoot[farFromRoot.Count - 1].Item1);
        // root에서 가장 먼 leaf가 두 개 이상이면 중간 값이 어차피 제일 먼 값
        if (farFromRoot[farFromRoot.Count - 1].Item2 == farFromRoot[farFromRoot.Count - 2].Item2)
        {
            return farFromLeaf[farFromLeaf.Count - 1].Item2;
        }
        // 그렇지 않으면 리프에서 두 번째로 멀리 떨어진 길이가 중간값
        else
        {
            return farFromLeaf[farFromLeaf.Count - 2].Item2;
        }
        
        return 0;
    }
    
    public List<(int, int)> BFS(List<int>[] graph, int start)
    {
        bool[] visited = new bool[n+1];
        List<(int, int)> distance = new List<(int, int)>();
        
        Queue<(int, int)> queue = new Queue<(int, int)>();
        queue.Enqueue((start, 0));
        visited[start] = true;
        
        while (queue.Count >= 1)
        {
            (int currNode, int dist) = queue.Dequeue();
            distance.Add((currNode, dist));
            
            foreach (int adjNode in graph[currNode])
            {
                if (!visited[adjNode])
                {
                    queue.Enqueue((adjNode, dist+1));
                    visited[adjNode] = true;
                } 
            }
        }
        
        return distance;
    }
}

결과