<Medium>Find the City With the Smallest Number of Neighbors at a Threshold Distance (LeetCode : C#)

https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/

📕 문제 설명

n개의 도시와 간선 정보 (from, to, weight)가 주어진다. 이때 도시간 양방향으로 이동 가능할 때, 각 도시별로 최대 distanceThreshold를 넘기지 않는 갈 수 있는 도시의 개수 중 가장 작은 수를 가지고 있는 도시 반환하기

• Input
  n, 간선 정보, distanceThreshold
• Output
  distanceThreshold 넘지 않은 가장 작은 수의 도달 가능한 도시를 가지는 도시 반환 (도시 개수가 같은 도시들 중에서는 도시 번호가 높은 곳 반환)
  

예제

풀이

public class Solution {
    public int FindTheCity(int n, int[][] edges, int distanceThreshold) {
        int[,] adj = new int[n,n];
        int[] result = new int[n];
        int min = int.MaxValue;
        int res = 0;
        for (int i = 0; i < edges.Length; i++) 
        {
            int[] edge = edges[i];
            adj[edge[0],edge[1]] = edge[2];
            adj[edge[1],edge[0]] = edge[2];
        }
        // 플로이드 워셜 -> 최단 거리 갱신
        for (int k = 0; k < n; k++) 
        {
            for (int i = 0; i < n; i++) 
            {
                for (int j = 0; j < n; j++) 
                {
                    if (adj[i,k] != 0 && adj[k,j] != 0 && (adj[i,k] + adj[k,j] < adj[i,j] || adj[i,j] == 0)) 
                    {
                        adj[i,j] = adj[i,k] + adj[k,j];
                    }
                }
            }
        }

        for (int i = 0; i < n; i++) 
        {
            for (int j = 0; j < n; j++) 
            {
                // distanceThreshold보다 작으면 count 해주기 
                if (i != j && adj[i,j] != 0 && adj[i,j] <= distanceThreshold) 
                {
                    result[i] = result[i] + 1;
                }
            }
        }

        // min보다 작거나 크면 갱신 (순서대로 봐서 greater은 보장됨)
        for (int i = 0; i < n; i++) 
        {
            if (result[i] <= min) 
            {
                min = result[i];
                res = i;
            }
        }

        return res;
    }
}

결과