파이썬으로 방향 그래프에서 가장 큰 색상 값 찾는 방법

문제 개요

n개의 색칠된 노드와 m개의 간선으로 이루어진 방향 그래프가 있다고 가정해 보겠습니다. 노드는 0부터 n-1까지 번호가 매겨져 있으며, 소문자로 구성된 문자열 col이 주어집니다. 여기서 col[i]는 그래프에서 i번째 노드(0 인덱스 기준)의 색상을 나타냅니다. 또한 간선 목록이 주어지는데, edges[j] = (u, v)는 u에서 v로 향하는 방향 간선이 존재함을 의미합니다.

그래프에서 유효한 경로(valid path)란 노드의 수열 x₁부터 xₖ까지에 대해 xᵢ에서 xᵢ₊₁로 향하는 방향 간선이 존재하는 경우를 말합니다. 경로의 색상 값은 해당 경로에서 가장 자주 등장하는 노드 색상의 빈도수입니다. 우리가 구해야 하는 것은 그래프 내 모든 유효한 경로 중에서 가장 큰 색상 값입니다. 만약 그래프에 사이클(cycle)이 존재한다면 -1을 반환해야 합니다.

예시

예를 들어 입력이 다음과 같다고 해봅시다.

col = "aabada"
edges = [(0,1),(1,4),(1,2),(2,3),(3,5),(4,5)]

이 경우 출력은 4가 됩니다. 경로 0 → 1 → 2 → 3 → 5가 색상 'a'를 포함하는 가장 긴 경로이며, 이 경로에는 'a'가 총 4번 등장하기 때문입니다.

풀이 접근 방식

이 문제는 위상 정렬(Topological Sort)과 동적 계획법(DP)을 결합하여 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

dp 테이블 정의: dp[i][c]는 노드 i에서 끝나는 경로 중 색상 c의 최대 출현 횟수를 저장합니다.
진입 차수 활용: 진입 차수(in-degree)가 0인 노드부터 큐에 넣어 위상 정렬 순서로 처리합니다.
점화식: 간선 u → v를 처리할 때, 모든 색상 c에 대해 dp[v][c] = max(dp[v][c], dp[u][c] + (c가 v의 색상이면 1, 아니면 0))로 갱신합니다.
사이클 판별: 최종적으로 방문한 노드 수가 전체 노드 수보다 작으면 사이클이 존재한다는 뜻이므로 -1을 반환합니다.

알고리즘 단계

n := col의 길이로 설정
간선 목록으로부터 graph(인접 리스트) 생성
indegree := 각 노드의 진입 차수를 저장하는 맵 생성
queue := 새로운 리스트 생성
dp := 크기가 n × 26인 배열을 만들고 0으로 초기화 (26은 알파벳 소문자 개수)
colorvalues := col의 각 문자를 알파벳 순서(0~25)로 변환한 리스트 생성
u를 0부터 n-1까지 반복하며, u가 indegree에 없으면(진입 간선이 없으면) 큐에 추가하고 dp[u][colorvalues[u]] := 1로 설정
visited := 0으로 초기화
큐가 비어 있지 않은 동안 반복:
- 큐에서 요소 u를 꺼내고 visited를 1 증가
- graph[u]의 각 v에 대해:
  - c를 0부터 25까지 반복하며 dp[v][c] = max(dp[v][c], dp[u][c] + (c == colorvalues[v]이면 1, 아니면 0))로 갱신
  - indegree[v]를 1 감소
  - indegree[v]가 0이 되면 v를 큐에 추가하고 indegree에서 삭제
visited < n이면 -1 반환 (사이클 존재)
dp 전체에서 최댓값 반환

구현 코드

아래 파이썬 코드를 통해 더 잘 이해해 보겠습니다.

from collections import defaultdict

def solve(col, edges):
    n = len(col)
    graph = defaultdict(list)
    indegree = defaultdict(int)

    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    queue = []
    dp = [[0]*26 for _ in range(n)]
    colorvalues = [ord(c) - ord("a") for c in col]

    for u in range(n):
        if u not in indegree:
            queue.append(u)
            dp[u][colorvalues[u]] = 1

    visited = 0
    while queue:
        u = queue.pop()
        visited += 1

        for v in graph[u]:
            for c in range(26):
                dp[v][c] = max(dp[v][c], dp[u][c] + (c == colorvalues[v]))
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
                del indegree[v]

    if visited < n:
        return -1
    return max(max(x) for x in dp)

col = "aabada"
edges = [(0,1),(1,4),(1,2),(2,3),(3,5),(4,5)]
print(solve(col, edges))

입력

"aabada", [(0,1),(1,4),(1,2),(2,3),(3,5),(4,5)]

출력

복잡도 분석

시간 복잡도: O(n × 26 + m × 26) — 각 노드와 간선마다 26개의 알파벳 색상을 처리하므로 사실상 O(n + m)에 비례합니다.
공간 복잡도: O(n × 26) — dp 테이블이 지배적인 공간을 차지합니다.

이 접근법은 위상 정렬을 통해 DAG(방향 비순환 그래프)의 특성을 활용하므로, 사이클이 있는 경우를 안정적으로 감지하면서도 각 경로별 색상 빈도를 효율적으로 추적할 수 있습니다.