인접 리스트(adjacency list) 형태로 표현된 방향 비순환 그래프(DAG, Directed Acyclic Graph)가 주어졌다고 가정해 봅시다. 이때 노드를 반복하지 않으면서 그래프에서 가장 긴 경로의 길이를 구하는 것이 목표입니다.
예를 들어 아래와 같은 그래프가 입력으로 주어진 경우,
경로 0 → 1 → 3 → 4 → 2의 길이가 4이므로 출력 결과는 4가 됩니다.
해결 접근 방법
이 문제는 깊이 우선 탐색(DFS)과 메모이제이션(Memoization)을 활용하면 효율적으로 해결할 수 있습니다. 각 노드에서 출발했을 때 도달할 수 있는 최장 경로 길이를 저장해 두면, 같은 노드를 여러 번 계산하는 낭비를 막을 수 있습니다.
알고리즘 단계
ans를 0으로 초기화합니다.n은 그래프의 노드 개수입니다.- 크기가 n인 리스트
table을 만들고 모든 값을 -1로 채웁니다. (-1은 아직 계산되지 않았음을 의미) - 노드 u를 인자로 받는 함수
dfs()를 정의합니다. table[u]가 -1이 아니라면 이미 계산된 값이므로 그대로 반환합니다.p_len을 0으로 초기화합니다.graph[u]에 연결된 각 정점 v에 대해 다음을 수행합니다.p_len = max(p_len, 1 + dfs(v))
table[u] = p_len으로 메모이제이션한 후p_len을 반환합니다.- 메인 로직에서는 0부터 n-1까지 모든 노드 i에 대해
ans = max(ans, dfs(i))를 수행합니다. - 최종적으로
ans를 반환하면 전체 그래프의 최장 경로 길이가 됩니다.
파이썬 구현 예제
다음 코드를 통해 더 자세히 이해해 보겠습니다.
class Solution: def solve(self, graph): ans = 0 n = len(graph) table = [-1] * n def dfs(u): if table[u] != -1: return table[u] p_len = 0 for v in graph[u]: p_len = max(p_len, 1 + dfs(v)) table[u] = p_len return p_len for i in range(n): ans = max(ans, dfs(i)) return ans ob = Solution() graph = [ [1, 2], [3, 4], [], [4], [2], ] print(ob.solve(graph))
입력
graph = [[1, 2],[3, 4],[],[4],[2]]
출력
4
시간 복잡도 분석
메모이제이션 덕분에 각 노드의 최장 경로는 한 번만 계산되며, 각 간선도 최대 한 번씩만 확인됩니다. 따라서 시간 복잡도는 O(V + E)(V는 노드 수, E는 간선 수)이고, 공간 복잡도 역시 O(V + E)입니다. DAG 특성상 사이클이 존재하지 않기 때문에 무한 재귀에 빠질 걱정 없이 안전하게 DFS를 적용할 수 있다는 점도 이 알고리즘의 큰 장점입니다.