Swift ) LeetCode(Medium) - Find the City With the Smallest Number of Neighbors at a Threshold Distance (Floyd - Warshall)

leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/discuss/?currentPage=1&orderBy=hot&query=

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

안녕하세요 후르륵짭짭 입니다.

이번에는 플로이드 워샬에 대해서 공부하려고 이 문제를 가져왔습니다.

 

** 플로이드 워샬 **

플로이드 워샬은 다익스트라 알고리즘 처럼 가중치를 가지고 최단거리를 구할 수 있는 알고리즘은데,

다익스트라는 우선순위 큐를 사용해서 최소값을 가져오는 반면

플로이드 워샬은 출발 점 - 중간 지점 - 도착 점 이렇게 세개의 점을 이용해서 최단 거리를 구하게 됩니다.

이렇게 있다면

연신내 - 종로3가 - 역곡 || 연신내 - 신도림 - 역곡

연신내 - 종로 3가 - 역곡은 이해가 되지만 연신내 - 신도림 - 역곡을 설명하자면

연신내 - 합정 - 신도림 을 구하면 연신내 - 신도림 - 역곡을 구할 수 있게 되는 겁니다.

 

그런데 예전에도 공부 했었지만,,, 왜 플로이드 워샬이 최단 거리를 구할 수 있을지,, 의문이였습니다.

이걸 실험 해보니 쉽게 이해 할 수 있었습니다.

Start는 시작 점,  middle은 중간지점 , End는 끝 지점을 의미합니다.

그래서 모든 경우를 테스트를 해보면 결국 도착점을 모두 N 번씩 점검해보는 것을 확인 할 수 있습니다.

0 - 0 - 0	(0,0)	1 - 0 - 0	(1,0)	2 - 0 - 0	(2,0)
0 - 0 - 1	(0,1)	1 - 0 - 1	(1,1)	2 - 0 - 1	(2,1)
0 - 0 - 2	(0,2)	1 - 0 - 2	(1,2)	2 - 0 - 2	(2,2)

0 - 1 - 0	(0,0)	1 - 1 - 0	(1,0)	2 - 1 - 0	(2,0)
0 - 1 - 1	(0,1)	1 - 1 - 1	(1,1)	2 - 1 - 1	(2,1)
0 - 1 - 2	(0,2)	1 - 1 - 2	(1,2)	2 - 1 - 2	(2,2)

0 - 2 - 0	(0,0)	1 - 2 - 0	(1,0)	2 - 2 - 0	(2,0)
0 - 2 - 1	(0,1)	1 - 2 - 1	(1,1)	2 - 2 - 1	(2,1)
0 - 2 - 2	(0,2)	1 - 2 - 2	(1,2)	2 - 2 - 2	(2,2)

 

** 문제 내용 **

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.

N개의 도시가 0 번 부터 N-1 까지 주어지고 배열 edges에는 (출발점 , 도착점, 가중치)가 양방향으로 주어집니다. 그리고 최대 거리 임계점인 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.

distanceThreshold 값 보다 작은 거리를 포함하고 있는 도시의 갯수가 가장 작은 값을 반환 하고 만약에 여러개라면 도시의 숫자가 높은 것을 반환하시오

 

** 코드 해설 **

class Solution {
    func findTheCity(_ n: Int, _ edges: [[Int]], _ distanceThreshold: Int) -> Int {
        
        var distanceMap = Array(repeating: Array(repeating: 10001, count: n), count: n)
       
        //초기설정
        for (_, yelement) in edges.enumerated(){
            
            let from = yelement[0]
            let to = yelement[1]
            let weight = yelement[2]
            
            distanceMap[from][to] = weight
            distanceMap[to][from] = weight
        
        }
        
        for node in 0..<n{
            distanceMap[node][node] = 0
        }
        
        //플로이드 워샬
        
        for middlePoint in 0..<n{
            
            for startPoint in 0..<n{
                
                for endPoint in 0..<n{
                    
                    if distanceMap[startPoint][middlePoint] + distanceMap[middlePoint][endPoint] < distanceMap[startPoint][endPoint]{
                        
                        distanceMap[startPoint][endPoint] = distanceMap[startPoint][middlePoint] + distanceMap[middlePoint][endPoint]
                        
                    }
                    
                    
                }
                
            }
            
        }
        
        var answer = 0
        var minValue = Int.max
        for (yindex , yelement) in distanceMap.enumerated(){
            
            var cnt = 0
            
            for (xindex , xelement) in yelement.enumerated(){
                
                if xindex != yindex{
                    
                    if xelement <= distanceThreshold{
                       cnt += 1
                    }
                    
                }
                
            }
            
            if minValue >= cnt {
                minValue = cnt
                answer = yindex
            }
            
        }
        
        return answer
    }
}

문제는 어렵지 않습니다.

일단 아래 처럼 초기 설정을 해줍니다. 그리고 자기위치는 값을 0으로 넣어줍니다.

 //초기설정
        for (_, yelement) in edges.enumerated(){
            
            let from = yelement[0]
            let to = yelement[1]
            let weight = yelement[2]
            
            distanceMap[from][to] = weight
            distanceMap[to][from] = weight
        
        }
        
        for node in 0..<n{
            distanceMap[node][node] = 0
        }

그리고 플로이드 워샬을 사용해서 각 도착점의 최단거리를 구해줍니다.

//플로이드 워샬
        
        for middlePoint in 0..<n{
            for startPoint in 0..<n{
                for endPoint in 0..<n{
                    
                    if distanceMap[startPoint][middlePoint] + distanceMap[middlePoint][endPoint] < distanceMap[startPoint][endPoint]{
                        
                        distanceMap[startPoint][endPoint] = distanceMap[startPoint][middlePoint] + distanceMap[middlePoint][endPoint]
                        
                    }   
                }   
            }   
        }

이렇게 하고 나서 마지막에 최소값을 가진 값을 찾고 계속 갱신해주면 됩니다.