[LeetCode] 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

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

leetcode - Find the City With the Smallest Number of Neighbors at a Threshold Distance

문제 유형 : 최단거리, 다익스트라, bfs

문제 난이도 : Medium

 

문제

There are n cities numbered from 0 to n-1. Given the array edges where edges[i] = [fromi, toi, weighti] represents a bidirectional and weighted edge between cities fromi and toi, and given the integer distanceThreshold.

Return the city with the smallest number of cities that are reachable through some path and whose distance is at most distanceThreshold, If there are multiple such cities, return the city with the greatest number.

Notice that the distance of a path connecting cities i and j is equal to the sum of the edges' weights along that path.

 

n 개의 도시가 0~n-1의 번호를 매겨왔다.

간선 정보 edges가 주어지는데, edges[i] = [from_i, to_i, weight]에서, from과 to 도시 사이에 weight만큼의 거리를 가진 양방향 길이 있다는 뜻이다.

그리고 정수 distanceThreshold가 주어진다.

 

한 도시에서 도달하능한 최소의 도시 개수가 가장 적은 도시를 반환하는데, 만약 개수가 같은 게 여럿 있다면, 그중 번호가 큰 도시를 반환하시오.

 

풀이

간선의 정보를 그래프로 변환한다.

그래프 정보를 기반으로, 각 노드에 대해서 bfs를 통해서 각 노드가 갈 수 있는 최대 도시수들을 구한다. 임계치 역시 반영해준다.

각 최대 도시수들을 보면서, 가장 적은 인접도시를 가진 도시를 반환하고, 순회 중 만약 기존 인접도시개수와 같은수의 도시가 있다면, 그 도시로 교체한다. 이 경우에 수는 업데이트 하지 않아도 된다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        vector<vector<pair<int, int>>> graph(n); // graph[from] = [[to, cost], [to, cost]]
        vector<int> boundaries(n, 0); // boundaries[i] = <number of neighbors>
        for(const auto &edge : edges) {
            int from = edge[0];
            int to = edge[1];
            int cost = edge[2];

            graph[from].push_back({to, cost});
            graph[to].push_back({from, cost});
        }

        for(int i = 0; i < n; i++) {
            vector<int> minDistance(n, INT_MAX);
            queue<int> q;
            q.push(i);
            minDistance[i] = 0;

            while(!q.empty()) {
                int currNode = q.front();
                q.pop();

                for(const auto &nextInfo : graph[currNode]) {
                    int nextNode = nextInfo.first;
                    int nextCost = nextInfo.second;

                    if(minDistance[currNode] + nextCost < minDistance[nextNode]) {
                        minDistance[nextNode] = minDistance[currNode] + nextCost;
                        
                        q.push(nextNode);
                    }
                }
            }

            int neighbor = 0;
            for(int j = 0; j < n; j++) {
                if(minDistance[j] <= distanceThreshold) neighbor++;
            }
            boundaries[i] = neighbor-1;
        }

        int ans = -1;
        int minNeighbor = INT_MAX;
        for(int i = 0; i < n; i++) {
            if(boundaries[i] < minNeighbor) {
                ans = i;
                minNeighbor = boundaries[i];
            } else if(boundaries[i] == minNeighbor) {
                ans = i;
            }
            cout << boundaries[i] << endl;
        }

        return ans;
    }
};