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

출처 : https://www.acmicpc.net/problem/2252

 

풀이 방법

위상 정렬 알고리즘을 통해 풀이할 수 있다.

위상 정렬 알고리즘이란 그래프에서 우선순위가 있는 작업을 할 때 순서를 정해주는 알고리즘이다 답이 여러 개가 될 수 있다.

조건으로 사이클이 없어야 한다. 

또한 최우선순위인 시작 점이 존재해야한다.

1. 진입 점이 0인 점을 큐에 넣어서 시작점으로 지정한다.
2. 큐에서 하나를 pop 하고 이와 연결된 노드의 진입 점을 -1 한다.
3. 만약 2번에서 진입 점을 -1 한 노드의 진입점이 0이면 큐에 추가한다.
4. 위 2~3번 과정을 N번 반복하는데 만약 N번 반복하기 전에 큐에 empty가 되면 사이클이 존재하는 경우이다.

코드

from collections import deque
N, M = map(int, input().split()) ## 학생 수, 비교 횟수
degree = [ 0 for _ in range(N + 1)] ## 들어 오는 거 초기화 
linked = [ [] for _ in range(N + 1)]
result = []

for i in range(M):
    a, b = map(int, input().split())
    degree[b] += 1
    linked[a].append(b)
queue = deque()

for i in range(1, N+1):
    if degree[i] == 0:
        queue.append(i) ## 시작 점 추가하기

for _ in range(N): ## N번 수행하기
    next = queue.popleft() ## 제일 왼쪽 제거하기
    result.append(next)
    for j in linked[next]:
        degree[j] -= 1 ## 진입점 끊기
        if degree[j] == 0:
            queue.append(j) ##  진입 점 0인 거 추가하기
for i in result:
    print(i, end = ' ')

degree는 현재 노드로 들어오는 노드의 수이다.

linked는 연결되어있는 노드의 쌍이다.