[백준]2252번 줄세우기 - python (위상정렬)

문제

 

 

 

이 문제를 풀기 위해서는 먼저 위상정렬이라는 개념을 알아햐한다

 

위상정렬이란?

위상 정렬(Topology Sort)이란 방향 그래프의 모든 노드를 방향성을 모두 지키며 순서대로 나열하는 것을 의미합니다. 

 

• 진입 차수(Indegree) : 특정한 노드로 들어오는 간선의 개수
• 진출 차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수

 

동작과정은

1. 진입차수가 0인 모든 노드를 큐에 넣고

2. 큐가빌 때까지 다음의 과정을 반복한다.

   1. 큐에서 원소를 꺼내고 해당 노드에서 나가는 간선을 그래프에서 제거한다.

   2. 새롭게 진입차수가 0이된 노드를 큐에 넣는다.

 

 

이렇게 되면 모든 노드의 방향성을 지켜가면서 순서대로 나열 할 수 있게 된다.

 

이때 시간 복잡도는 모든 노드를 확인하며 해당 노드와 연결된 간선을 제거해야하므로 시간복잡도 O(V+E)가 됩니다.

 

 

정답코드

# 알고리즘 -> 이분탐색? 큐? 스택?
from collections import deque
n,m = map(int,input().split())
graph = [[]for i in range(n+1)]
degree = [0 for i in range(n+1)]
answer = []
q = deque()

for i in range(m):
    a, b = map(int,input().split())
    graph[a].append(b)
    degree[b] += 1
#진입차수가 0인 애들 먼저 큐에 삽입
for i in range(1,n+1):
    if degree[i] == 0:
        q.append(i)

while q:
    tmp = q.popleft()
    answer.append(tmp)
    #해당 노드와 연결된 간선 제거
    for i in graph[tmp]:
        degree[i] -= 1
        if degree[i] == 0:
            q.append(i)

print(*answer)