알고리즘 스터디

[백준] 2252 줄 세우기 - 위상 정렬 파이썬

문제

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

 

2252번: 줄 세우기

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의

www.acmicpc.net

 

 


풀이

https://freedeveloper.tistory.com/390

 

[이것이 코딩 테스트다 with Python] 36강 위상 정렬

4https://www.youtube.com/watch?v=xeSz3pROPS8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=36 위상 정렬 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미..

freedeveloper.tistory.com

 

위상정렬 알고리즘

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

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

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

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

=> 결과 적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다

 

 

위상정렬 특징

  • 사이클이 존재하지 않은 방향그래프에서만 수행가능
  • 여러가지 답이 존재
  • 스택&DFS로도 수행가능

 

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

n, m = map(int, input().split())

#그래프 만들기
g = [[] for _ in range(n+1)]
indgree = [0]*(n+1)
for _ in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    indgree[b] += 1

#큐에 초기 진입차수 0인 노드 넣기
q = deque()
for i in range(1, n+1):
    if indgree[i] == 0:
        q.append(i)

#위상정렬
while q:
    now = q.popleft()
    print(str(now) + " ", end="")
    for i in g[now]:
        indgree[i] -= 1
        if indgree[i] == 0: #새롭게 진입차수 0이 된 노드 넣기
            q.append(i)