Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 임계 거리 내 이웃 도시 수가 가장 적은 도시 찾기 (플로이드-워셜 알고리즘)

0부터 n-1까지 번호가 매겨진 n개의 도시가 있다고 가정해 봅시다. 배열 edges가 주어지며, edges[i] = [fromi, toi, weighti]는 fromi와 toi 두 도시 사이의 양방향 가중치 간선을 나타냅니다. 또한 정수형 distanceThreshold(거리 임계값)가 주어집니다.

이때 우리가 찾아야 하는 것은, 어떤 경로를 통해 도달 가능하면서 그 거리가 distanceThreshold 이하인 도시들의 개수가 가장 적은 도시입니다. 만약 그런 도시가 여러 개라면, 번호가 가장 큰 도시를 반환해야 합니다.

예를 들어 다음과 같은 입력이 주어졌다고 해보겠습니다.

n = 4이고 distanceThreshold = 4일 때, 출력은 3이 됩니다. 그 이유는 다음과 같습니다.

각 도시별로 거리 임계값 4 이내에 있는 이웃 도시들을 살펴보면:

C0 -> [C1, C2]
C1 -> [C0, C2, C3]
C2 -> [C0, C1, C3]
C3 -> [C1, C2]

도시 0과 도시 3은 모두 임계값 4 이내에 이웃 도시가 2개씩 있습니다. 하지만 조건상 더 큰 번호를 반환해야 하므로 정답은 3입니다.

문제 해결 접근 방법

이 문제는 플로이드-워셜(Floyd-Warshall) 알고리즘을 활용하면 효율적으로 해결할 수 있습니다. 플로이드-워셜은 모든 쌍의 최단 경로를 O(n³) 시간 복잡도로 구할 수 있기 때문입니다.

알고리즘 단계

  • n x n 크기의 정사각 행렬 dp를 선언하고 모든 값을 무한대(INF)로 초기화합니다.
  • 그래프의 인접 행렬(비용 행렬)을 생성하여 dp에 저장합니다.
  • ret := 0, cnt := 무한대로 초기화합니다.
  • k를 0부터 n-1까지 반복합니다:
    • i를 0부터 n-1까지 반복합니다:
      • j를 0부터 n-1까지 반복합니다:
        • i와 j가 같으면 다음 반복으로 넘어갑니다.
        • dp[i][j] > dp[i][k] + dp[k][j]라면:
          • dp[j][i] := dp[i][k] + dp[k][j]
          • dp[i][j] := dp[i][k] + dp[k][j]
  • i를 0부터 n-1까지 반복합니다:
    • temp := 0으로 초기화합니다.
    • j를 0부터 n-1까지 반복하며, dp[i][j] <= t이면 temp를 1 증가시킵니다.
    • temp <= cnt이면 cnt := temp, ret := i로 갱신합니다.
  • ret을 반환합니다.

C++ 구현 예제

다음 구현 코드를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& e, int t) {
        vector<vector<int>> dp(n, vector<int>(n, 1e7));
        for(int i = 0; i < e.size(); i++){
            int u = e[i][0];
            int v = e[i][1];
            int w = e[i][2];
            dp[u][v] = w;
            dp[v][u] = w;
        }
        int ret = 0;
        int cnt = INT_MAX;
        for(int k = 0; k < n; k++){
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    if(i == j) continue;
                    if(dp[i][j] > dp[i][k] + dp[k][j]){
                        dp[j][i] = dp[i][j] = (dp[i][k] + dp[k][j]);
                    }
                }
            }
        }
        for(int i = 0; i < n; i++){
            int temp = 0;
            for(int j = 0; j < n; j++){
                temp += (dp[i][j] <= t);
            }
            if(temp <= cnt){
                cnt = temp;
                ret = i;
            }
        }
        return ret;
    }
};
main(){
    vector<vector<int>> v = {{0,1,3},{1,2,1},{1,3,4},{2,3,1}};
    Solution ob;
    cout << (ob.findTheCity(4, v, 4));
}

입력

4
[[0,1,3],[1,2,1],[1,3,4],[2,3,1]]
4

출력

3

코드 설명 및 시간 복잡도

위 코드에서 먼저 인접 행렬을 무한대 값(1e7)으로 초기화한 뒤, 주어진 간선 정보로 양방향 가중치를 설정합니다. 이후 플로이드-워셜 알고리즘의 삼중 반복문을 통해 모든 도시 쌍 사이의 최단 거리를 계산합니다.

최단 거리 계산이 완료되면, 각 도시마다 임계값 t 이내로 도달 가능한 도시의 개수를 세어 비교합니다. 이웃 수가 가장 적은 도시를 찾되, 동률일 경우 더 큰 번호의 도시가 선택되도록 temp <= cnt 조건으로 처리했습니다.

시간 복잡도: O(n³)
공간 복잡도: O(n²)