-
Notifications
You must be signed in to change notification settings - Fork 2
/
가장 먼 노드.kt
58 lines (46 loc) · 1.57 KB
/
가장 먼 노드.kt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/* https://programmers.co.kr/learn/courses/30/lessons/49189 */
/* 최단 거리 */
import java.util.*
class Solution {
fun solution(n: Int, edges: Array<IntArray>): Int {
val graph = Array(n + 1) { mutableListOf<Int>() }
edges.forEach { (node1 ,node2) ->
graph[node1].add(node2)
graph[node2].add(node1)
}
val minDist: IntArray = getMinDistArray(graph, 1)
return getLongestNodeCount(minDist)
}
// 다익스트라
private fun getMinDistArray(graph: Array<MutableList<Int>>, srcNode: Int): IntArray {
val minDist = IntArray(graph.size) { -1 }
val q: Queue<Int> = LinkedList()
minDist[1] = 0
q.offer(1)
while (q.isNotEmpty()) {
val midNode = q.poll()
for (toNode in graph[midNode]) {
val nextDist = minDist[midNode] + 1
if (minDist[toNode] == -1 || minDist[toNode] > nextDist) {
minDist[toNode] = nextDist
q.offer(toNode)
}
}
}
return minDist
}
// 가장 먼 노드 개수 계산
private fun getLongestNodeCount(minDist: IntArray): Int {
var longestDist = 0
var count = 0
minDist.forEach { dist ->
if (longestDist < dist) {
longestDist = dist
count = 1
} else if (longestDist == dist) {
count++
}
}
return count
}
}