문제) 백준 - 위상 정렬 (Topology Sort) - 줄 세우기
-> 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
전형적인 위상 정렬 문제. 각 학생들의 키 비교를 진입 차수로 생각하여 위상 정렬하면 된다.
소스 코드)
from collections import deque
v, e = map(int, input().split())
#진입 차수
indegree = [0] * (v + 1)
graph = [[] for i in range(v + 1)]
for _ in range(e):
a, b = map(int, input().split())
graph[a].append(b)
indegree[b] += 1
def topology_sort():
result = []
q = deque()
#진입 차수가 0인 학생 탐색
for i in range(1, v + 1):
if indegree[i] == 0:
q.append(i)
while q:
now = q.popleft()
result.append(now)
for i in graph[now]:
indegree[i] -= 1
if indegree[i] == 0:
q.append(i)
for i in result:
print(i, end=' ')
topology_sort()
반응형
'PS(Problem Solving) > 백준_BOJ' 카테고리의 다른 글
[백준] 11725번 - 트리의 부모 (파이썬) (0) | 2021.03.12 |
---|---|
[백준] 12865번 - 평범한 배낭 (파이썬, C++) (0) | 2021.03.11 |
[백준] 11054번 - 가장 긴 바이토닉 부분 수열 (파이썬) 문제 및 풀이 (0) | 2021.03.09 |
[백준] 11722번 - 가장 긴 감소하는 부분 수열 (C++, 파이썬) 문제 및 풀이 (0) | 2021.03.09 |
[백준] 1890번 - 점프 (파이썬) 문제 및 풀이 (0) | 2021.03.09 |
댓글