📝 BaekJoon 2252번 : 줄 세우기 (G3 57.112%)
🔎 줄 세우기 문제
📌 아이디어
위상정렬(Topological Sorting) 알고리즘을 이용한 기본문제이다.
💭 풀이
- 먼저 위상정렬(Topological Sorting)이란 유향 그래프의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 쉽게 말하면 '순서가 정해져있는 작업'을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다.
- 위상정렬 알고리즘의 특징으로는 진입차수를 계산한다는 특징을 가진다. 위상정렬은 사이클이 없는 그래프에서 가능하기 때문에 진입차수가 0인 그래프가 1개이상 존재한다.
- 진입차수가 0인 노드들을 먼저 큐에 넣고 해당 큐에 연결된 노드들과의 연결을 끊는 의미로 진입차수를 -1해준다. 만약 해당 노드가 진입차수가 0일 때 q에 넣어주게 된다.
- 그렇게 q에 들어온 순서대로가 위상정렬된 상태이며 현재 순서가 우선순위로 정렬된 작업이 된다.
- 만약 숫자가 낮은 우선순위가 전제로 되어있다면 deque 자료구조대신 heapq 자료구조를 이용할 수 있다.
💻 코드
import heapq, sys
input = sys.stdin.readline
n, m = map(int,input().split())
node = [[] for _ in range(n+1)]
indegree = [0]*(n+1)
for _ in range(m) :
a, b = map(int,input().split())
node[a].append(b)
indegree[b] += 1
q = []
for i in range(n+1) :
if i != 0 and indegree[i] == 0 :
heapq.heappush(q,i)
result = []
while q :
x = heapq.heappop(q)
result.append(x)
for i in node[x] :
indegree[i] -= 1
if indegree[i] == 0 :
heapq.heappush(q,i)
print(*result)
owei