on
1334. Find the City With the Smallest Number of Neighbors at a...
1334. Find the City With the Smallest Number of Neighbors at a...
class Solution {
func findTheCity(_ n: Int , _ edges: [[ Int ]], _ distanceThreshold: Int ) - > Int {
let INF: Int = Int ( 1e9 )
var graph: [[ Int ]] = Array(repeating: Array(repeating: INF, count: n), count: n)
// i에서 i로 가는 경우 0으로 설정
for i in 0. . < n {
graph[i][i] = 0
}
// graph 배열에 weight 설정
for edge in edges {
graph[edge[ 0 ]][edge[ 1 ]] = edge[ 2 ]
graph[edge[ 1 ]][edge[ 0 ]] = edge[ 2 ]
}
// 플로이드 워셜 알고리즘 적용
for k in 0. . < n {
for i in 0. . < n {
for j in 0. . < n {
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
}
}
}
var minCnt: Int = INF
var res: Int = 0
// 각 노드 별로 distanceThreshold보다 적은 거리에 있는 노드의 갯수를 카운트해서 res 갱신
for i in 0. . < n {
let cnt: Int = graph[i].filter() { $0 < = distanceThreshold }.count
if cnt < = minCnt {
minCnt = cnt
res = i
}
}
return res
}
}
from http://one10004.tistory.com/83 by ccl(A) rewrite - 2021-11-12 03:00:57