1857. Largest Color Value in a Directed Graph

[zeikar]

Problem link

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

Problem Summary

노드에 색이 칠해져 있는 방향 그래프가 주어진다.
그래프의 path 중 가장 많이 나온 색깔의 개수를 구하는 문제. 사이클이 있다면 -1을 출력.

Solution

처음엔 dfs로 구현해서 제출했는데 엣지 케이스 처리가 까다롭다. (사이클 탐지, visited 체크 등)
결국 위상 정렬로 다시 제출.

그리디적인 방법을 생각해보면 가장 색깔이 많이 나오려면 경로의 제일 처음부터 돌려야 한다. 경로의 시작 지점은 위상 정렬로 쉽게 구할 수 있다.
사이클 탐지도 꽤 간단한데, 위상 정렬을 했을 때 방문하지 못하는 노드는 사이클이 존재하는 것이다.

색깔 카운트는 자기 자신은 ++, 다음 노드는 이전 노드의 값 중 최댓값을 복사해 줌.

Source Code

from typing import List


class Solution:
    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:

        graph = {}
        indegree = [0] * len(colors)
        for edge in edges:
            graph[edge[0]] = graph.get(edge[0], []) + [edge[1]]
            indegree[edge[1]] += 1
        color_cnt = [[0] * 26 for i in range(len(colors))]
        queue = []

        for i in range(len(colors)):
            if indegree[i] == 0:
                queue.append(i)

        max_value = 0
        processed = 0
        while queue:
            processed += 1
            node = queue.pop(0)

            color_cnt[node][ord(colors[node]) - ord('a')] += 1

            for child in graph.get(node, []):
                indegree[child] -= 1
                for j in range(26):
                    color_cnt[child][j] = max(color_cnt[child][j], color_cnt[node][j])

                if indegree[child] == 0:
                    queue.append(child)

            max_value = max(max_value, max(color_cnt[node]))

        return max_value if processed == len(colors) else -1