[BOJ] 줄 세우기

---

코드

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]    # 간선 정보
indegree = [0]*(n+1)    # 각 노드의 진입차수

# 간선정보와 진입차수 설정
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1

# 위상정렬
def topology_sort():
    result = []
    q = deque()

    # 초기설정: 진입차수가 0인 노드를 큐에 push
    for i in range(1, n+1):
        if indegree[i] == 0:
            q.append(i)

    # 큐에서 노드를 꺼내어 그래프에서 간선을 제거하고 진입차수가 0이 되는 노드를 큐에 추가
    # 모든 노드를 방문하기 전에 큐가 비면 사이클이 존재한다는 의미임
    while q:
        v = q.popleft()
        result.append(v)
        for adj in graph[v]:
            indegree[adj] -= 1
            if indegree[adj] == 0:
                q.append(adj)

    return result

result = topology_sort()
print(' '.join(list(map(str, result))))

결과

풀이 방법

• 위상정렬 알고리즘을 공부하였다.
• 위상정렬이란 사이클이 발생하지 않는 방향그래프에서 노드들을 간선 방향을 거스르지 않게 나열하는 것을 의미한다.
• 위상정렬 알고리즘은 주로 큐를 사용하여 구현하며, 진입차수(현재 노드로 들어오는 간선 개수)라는 개념이 사용되고 과정은 아래와 같다.
• 1. 먼저 진입차수가 0인 노드를 큐에 push한다.
• 2. 큐에서 노드를 꺼내어 그래프에서 간선을 제거하고 진입차수가 0이 되는 노드를 큐에 push한다. 꺼낸 노드를 결과에 추가한다.
• 3. 위 과정을 큐에 원소가 없을 때까지 반복한다.
• 만약 큐가 비었는데 그래프에 남아있는 노드가 있다면 진입차수가 0이 될 수 없는 노드가 있고, 이는 사이클이 존재한다는 의미이다.

---