053 줄 세우기

첫번째 코드

 

위상정렬이라는 것을 처음 접했는데,

사실 어디에 사용해야 좋을지 의문이었다.

 

이전에 배운 정렬들이 많아서 문제를 보고 살짝 감을 잡았다.

세어야 하는 순서가 있는 경우에 적용하면 효율적일 것 같다.

 

개념 그대로 적용하는 코드가 작성된다.

이전의 queue를 이용해서 정렬하는 방식으로 어렵다고 생각이 들지는 않았다.

 

from collections import deque

n, m = map(int, input().split())
A = [[] for _ in range(n+1)]
indegree = [0] * (n+1)

for i in range(m):
    s, e = map(int, input().split())
    A[s].append(e)
    indegree[e] += 1

queue = deque()

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

while queue:
    now = queue.popleft()
    print(now, end = ' ')

    for next in A[now]:
        indegree[next] -= 1
        if indegree[next] == 0:
            queue.append(next)

 

통과!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/2252.%E2%80%85%EC%A4%84%E2%80%85%EC%84%B8%EC%9A%B0%EA%B8%B0

programmers/백준/Gold/2252. 줄 세우기 at main · ornni/programmers