2252: 줄 세우기

문제 링크

2252: 줄 세우기

구현 방식

• 위상 정렬 기본 구현 문제이다
  • 위상 정렬: 사이클이 없는 방향 그래프(DAG)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열
  • 진입차수(indegree): 특정한 노드로 들어오는 간선의 개수
  • 진출차수(outdegree): 특정한 노드에서 나가는 간선의 개수
  • 위상 정렬 알고리즘
    • 1. 진입 차수가 0인 모든 노드를 Queue에 넣음
    • 2. Queue가 빌 때까지,
      • 노드(cur)를 하나 꺼내어 해당 노드에서 나가는 간선을 제거(indegree[cur] -= 1)
      • indegree가 0이 된 노드를 Queue에 추가
    • 각 노드가 Queue에 들어온 순서가 위상 정렬의 결과
  • 모든 노드를 방문하기 전에 Queue가 빈다면 cycle이 존재하는 경우임

코드

import sys
from collections import deque

V, E = map(int, sys.stdin.readline().strip().split())

indegree = [0] * (V+1) #모든 노드에 대한 진입차수 0으로 초기화
graph = [[] for v in range(V+1)]
for e in range(E):
    u, v = map(int, sys.stdin.readline().strip().split())
    graph[u].append(v)
    indegree[v] += 1

def topology_sort():
    queue = deque()

    for v in range(1, V+1): #진입차수가 0인 노드를 큐에 삽입
        if indegree[v] == 0: queue.append(v)
    
    while queue:
        cur = queue.popleft()
        result.append(cur)

        for nex in graph[cur]:
            indegree[nex] -= 1
            if indegree[nex] == 0: queue.append(nex)

result = []
topology_sort()
print(" ".join(map(str, result)))