🟩 [백준] [Python] [Gold3] 2252번_줄 세우기

문제

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

2252번: 줄 세우기

풀이

# 백준 2252번 문제 - 줄 세우기 
from collections import deque
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
inDegree = [0] * (n+1)
q = deque()
answer = []
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    inDegree[b] += 1

for i in range(1, n+1):
    if inDegree[i] == 0:
        q.append(i)

while q:
    temp = q.popleft()
    answer.append(temp)
    for i in graph[temp]:
        inDegree[i] -= 1
        if inDegree[i] == 0:
            q.append(i)
print(*answer)

위상정렬 알고리즘을 사용해야 하는 문제이다.

위상정렬은 처음 접해서 구글링을 통해 문제를 해결하였다. 

 

inDegree는 앞의 노드와 연결되어 있는 수를 세는 변수이다. inDegree가 0 이면 큐에 넣어준다. 

큐가 빌 때 까지 while 문을 돌면서 q의 앞에 있다면 먼저 나와야 하는 학생이다. 

인덱스를 통해 그래프의 모든 학생을 탐색 후 앞에 와야하는 학생이 없다면 출력해주도록 한다.