문제 이해하기
정점이 n개인 방향 비순환 그래프(Directed Acyclic Graph, DAG)가 주어졌다고 가정해 봅시다. 정점은 0부터 n-1까지 번호가 매겨져 있으며, 그래프는 간선 리스트 형태로 표현됩니다. 여기서 edges[i] = (u, v)는 노드 u에서 노드 v로 향하는 방향 간선을 의미합니다.
우리가 구해야 하는 것은 그래프의 모든 노드에 도달할 수 있는 가장 작은 정점 집합입니다. 결과는 어떤 순서로 반환해도 무방합니다.
예를 들어 입력이 다음과 같다면,
출력은 [0, 2, 3]이 됩니다. 이 세 정점은 다른 어떤 정점에서도 도달할 수 없는 노드들이기 때문입니다. 즉, 이 정점들에서 탐색을 시작하면 그래프 전체를 커버할 수 있습니다.
접근 방법: 진입 간선이 없는 정점 찾기
핵심 아이디어는 아주 단순합니다. 바로 들어오는 간선(진입 간선)이 하나도 없는 정점을 찾는 것입니다.
DAG에서 정점 u에서 정점 v로 가는 간선이 존재한다면, v는 u로부터 도달 가능하므로 시작점으로 선택할 필요가 없습니다. 반대로 진입 간선이 없는 정점은 다른 어느 정점에서도 도달할 수 없으므로 반드시 시작 집합에 포함되어야 합니다. 결국 정답은 "진입 차수(in-degree)가 0인 정점들의 집합"과 같습니다.
알고리즘 단계
- 전체 정점의 집합 all_nodes를 생성합니다 (0부터 n-1까지).
- 간선 리스트를 순회하면서 각 간선의 도착 정점을 별도의 집합 v에 추가합니다.
- all_nodes에서 v에 포함된 정점, 즉 진입 간선이 있는 정점들을 제거합니다.
- 남은 정점 집합을 반환합니다.
예제 코드
def solve(edges):
n = len(edges)
all_nodes = set(range(n))
v = set()
for edge in edges:
v.add(edge[1])
ans = all_nodes - v
return ans
edges = [(0,1),(2,1),(3,1),(1,4),(2,4)]
print(solve(edges))입력
[(0,1),(2,1),(3,1),(1,4),(2,4)]
출력
{0, 2, 3}참고 사항 및 복잡도 분석
위 코드에서는 예제의 특성상 정점 개수와 간선 개수가 같아 len(edges)를 정점 수로 사용했습니다. 실제 문제에서는 정점의 개수 n이 별도의 매개변수로 주어지는 경우가 일반적이며, 이 경우 solve(edges, n) 형태로 받아 처리하면 더 안전합니다.
시간 복잡도는 간선 리스트를 한 번만 순회하므로 O(E)이며, 공간 복잡도는 정점 집합을 저장해야 하므로 O(V)입니다. 여기서 V는 정점의 수, E는 간선의 수입니다.