알고리즘 분류

  • 그래프 알고리즘 (유향 그래프)
  • 사이클 판단

알고리즘 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from collections import deque

v, e = map(int, input().split())
graph = [[] for _ in range(v + 1)]
indegree = [0] * (v + 1)

for i in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1

result = []
q = deque()

# 진입 차수가 0인 정점을 큐에 추가
for i in range(1, v + 1):
    if indegree[i] == 0:
        q.append(i)

# 큐가 빌 때까지 반복
while q:
    now = q.popleft()
    result.append(now)

    # 큐에서 뽑은 원소와 연결된 노드들의 진입차수를 1 빼기
    for i in graph[now]:
        indegree[i] -= 1
        # 새롭게 진입 차수가 0이 되는 노드를 큐에 삽입
        if indegree[i] == 0:
            q.append(i)

if len(result) != v:
    print('사이클 발생')
else:
    for x in result:
        print(x, end=' ')

설명

위상 정렬

방향 그래프의 모든 노드를 방향성에 거르스지 않도록 순서대로 나열하는 것

유향 비순환 그래프 (출처)

유향 비순환 그래프(Directed Acyclic Graph, DAG)는 수학, 컴퓨터 과학 분야의 용어의 하나로서 사이클이 없는 유향 그래프이다. 즉, 각 간선은 하나의 꼭짓점에서 다른 꼭짓점으로 방향을 잇는데 이처럼 어떠한 꼭짓점 v에서 시작하여 끝내 다시 v로 돌아가 순환 반복되는 일정한 방향의 일련한 간선을 따라가는 방법이 없는 그래프를 의미한다. 또한 사이클이 없는 방향그래프라는 정의를 통해 모든 트리는 DAG임을 알 수 있다. (어떤 그래프가 주어졌을 때 이 그래프가 DAG인지 판단하기 위해서는 사이클의 존재여부를 확인하면 된다.)

위상 정렬이 가능한 유향 그래프는 비순환 그래프이다

위상 정렬을 할 수 있다 → 유향 비순환 그래프

절차

  1. 진입 차수가 0인 노드를 큐에 넣는다.
  2. 큐가 빌 때까지 다음의 과정을 반복한다.
    1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
    2. 새롭게 진입차수가 0이 된 노드를 큐에 집어 넣는다.
  3. 제거한 순서대로 나열하면 정렬된 순서이다.

유향 그래프에서 사이클 판단

큐에서 원소가 V번 추출되기 전에 큐가 비어버리면 사이클이 발생한 것

참고 레퍼런스

이것이 코딩테스트다 with 파이썬 (나동빈, 2021)

유향 비순환 그래프 (AlgorFati)