[LeetCode] 1857. Largest Color Value in a Directed Graph

https://leetcode.com/problems/largest-color-value-in-a-directed-graph/description/?envType=daily-question&envId=2025-05-26

leetcode - Largest Color Value in a Directed Graph

문제 유형: 위상 정렬, BFS, 다이나믹 프로그래밍

문제 난이도: Hard

 

문제

There is a directed graph of n colored nodes and m edges. The nodes are numbered from 0 to n - 1.

You are given a string colors where colors[i] is a lowercase English letter representing the color of the ith node in this graph (0-indexed). You are also given a 2D array edges where edges[j] = [aj, bj] indicates that there is a directed edge from node aj to node bj.

A valid path in the graph is a sequence of nodes x1 -> x2 -> x3 -> ... -> xk such that there is a directed edge from xi to xi+1 for every 1 <= i < k. The color value of the path is the number of nodes that are colored the most frequently occurring color along that path.

Return the largest color value of any valid path in the given graph, or -1 if the graph contains a cycle.

 

풀이

freq[i][c] = i까지 순회해오면서의 c글자의 최대 개수로 지정한다.

위상 정렬 + DP라.. 매우 신박하게 돌아간다.

위상정렬을 하면서, freq테이블을 업데이트 하는데, 각 글자별 최대값만, 즉 최선의 결과로 병합시킨다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int init = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    return 0;
}();

class Solution {
public:
    int largestPathValue(string colors, vector<vector<int>>& edges) {
        int n = colors.size();
        vector<vector<int>> adj(n);
        vector<int> indegree(n);
        vector<bool> visited(n, 0);
        for(const auto &edge : edges) {
            int u = edge[0];
            int v = edge[1];

            adj[u].emplace_back(v);
            indegree[v]++;
        }

        vector<array<int, 26>> freqs(n);
        queue<int> q;
        for(int i = 0; i < n; i++) {
            if(indegree[i] == 0) {
                q.emplace(i);
                freqs[i][colors[i] - 'a'] = 1;
                visited[i] = true;
            }
        }

        int ans = -1;
        while(!q.empty()) {
            int curr = q.front();
            q.pop();

            for(const auto &next : adj[curr]) {
                int nextColor = colors[next] - 'a';
                for(int i = 0; i < 26; i++) {
                    int add = i == nextColor? 1:0;
                    if(freqs[curr][i] + add  > freqs[next][i]) {
                        freqs[next][i] = freqs[curr][i] + add;
                    }
                }
                if(--indegree[next] == 0) {
                    q.emplace(next);
                    visited[next] = true;
                }
            }
            ans = max(ans, *max_element(freqs[curr].begin(), freqs[curr].end()));
        }

        for(int i = 0; i < n; i++) if(!visited[i]) return -1;
        return ans;
    }
};

 

Go

func largestPathValue(colors string, edges [][]int) int {
    n := len(colors)
    adj := make([][]int, n)
    freqs := make([][]int, n)
    for i := 0; i < n; i++ {
        adj[i] = make([]int, 0)
        freqs[i] = make([]int, 26)
    }
    indegree := make([]int, n)
    visited := make([]bool, n)

    for _, edge := range edges {
        adj[edge[0]] = append(adj[edge[0]], edge[1])
        indegree[edge[1]]++
    }

    ans := -1
    q := make([]int, 0)
    for i, ind := range indegree {
        if ind == 0 {
            q = append(q, i)
            freqs[i][int(colors[i] - 'a')] = 1
            visited[i] = true
        }
    }

    for len(q) > 0 {
        curr := q[0]
        q = q[1:]

        for _, next := range adj[curr] {
            nextColor := int(colors[next] - 'a')
            for i := 0; i < 26; i++ {
                newVal := freqs[curr][i]
                if i == nextColor {
                    newVal++
                }
                freqs[next][i] = max(freqs[next][i], newVal)
            }
            indegree[next]--
            if indegree[next] == 0 {
                q = append(q, next)
                visited[next] = true
            }
        }

        for i := 0; i < 26; i++ {
            ans = max(ans, freqs[curr][i])
        }
    }

    for i := 0; i < n; i++ {
        if !visited[i] {
            return -1
        }
    }

    return ans
}

 

Python3

from collections import deque
class Solution:
    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
        n = len(colors)
        adj = [[] for _ in range(n)]
        freqs = [[0]*26 for _ in range(n)]
        visited = [False] * n
        indegree = [0] * n

        for edge in edges:
            adj[edge[0]].append(edge[1])
            indegree[edge[1]] += 1

        ans = -1
        q = deque()
        for i in range(n):
            if indegree[i] == 0:
                q.append(i)
                freqs[i][ord(colors[i]) - ord('a')] = 1
                visited[i] = True

        while q:
            curr = q.popleft() 
            for nextNode in adj[curr]:
                for i in range(26):
                    add = 1 if i == ord(colors[nextNode]) - ord('a') else 0
                    newVal = freqs[curr][i] + add
                    freqs[nextNode][i] = max(freqs[nextNode][i], newVal)
                indegree[nextNode] -= 1
                if indegree[nextNode] == 0:
                    q.append(nextNode)
                    visited[nextNode] = True
            ans = max(ans, max(freqs[curr]))
        
        for v in visited:
            if not v:
                return -1
        
        return ans