Daily LeetCode Challenge - 1857. Largest Color Value in a Directed Graph

Problem From.
https://leetcode.com/problems/largest-color-value-in-a-directed-graph/

오늘 문제는 그래프가 주어졌을때, 그 그래프를 따라서 탐색하면서 가장 많은 색상이 나온 횟수를 반환하는 문제였다.

이 문제는 BFS 를 통해서 풀었는데, 먼저 주어진 배열을 그래프의 형태로 바꾸어두고, 색상은 abc 의 알파벳 소문자 형태로 나오므로 먼저 알파벳 길이만큼의 색상 배열을 선언해두고, 그래프를 탐색하면서 색상이 나온 횟수를 기록해둔다. 마지막으로 색상 배열에서 가장 많이 나온 숫자를 찾아서 리턴해준다.

class Solution {
    fun largestPathValue(colors: String, edges: Array<IntArray>): Int {
        // also serves as the number of vertices
        val lenC = colors.length

        // not used
        // val nEdges = edges.size
        
        val (graph, indegrees) = buildGraph(lenC, edges)
        
        val chToChFreqs = Array(lenC){ IntArray(26) }
        
        val queue = LinkedList<Int>()
        for ((idx, indegree) in indegrees.withIndex()){
            if(indegree == 0){
                queue.offer(idx)
                chToChFreqs[idx][colors[idx] - 'a'] = 1
            }
        }
        
        var seen = 0
        var largest = 0
    
        while(queue.isNotEmpty()){
            val cur = queue.poll()
            ++seen
            
            largest = maxOf(largest, chToChFreqs[cur].max()!!)
            
            graph[cur]?.let{
                for (next in it){
                    for (i in 0 until 26){
                        chToChFreqs[next][i] = maxOf(chToChFreqs[next][i], chToChFreqs[cur][i] + if(colors[next] - 'a' == i) 1 else 0)
                    }
                    
                    if(--indegrees[next] == 0)
                        queue.offer(next)
                }
            }
        }
        
        return if(seen == lenC) largest else -1
    }
    
    fun buildGraph(nVertices: Int, edges: Array<IntArray>): Pair<Map<Int, HashSet<Int>>, IntArray>{
        val graph = HashMap<Int, HashSet<Int>>()
        val indegrees = IntArray(nVertices){ 0 }
        
        for((u, v) in edges){
            graph.getOrPut(u){HashSet()}.add(v)
            ++indegrees[v]
        }
        
        return Pair(graph, indegrees)
    }
}