Computer Science/알고리즘
[백준 - Python] 2252 - 줄 세우기
바보1
2023. 8. 20. 22:56
0. 문제 링크
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
1. 풀이 방법
2023.08.13 - [Computer Science/알고리즘] - [백준 - Python] 1766 - 문제집
[백준 - Python] 1766 - 문제집
0. 문제 링크 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄
hi-guten-tag.tistory.com
위의 문제처럼 위상 정렬을 사용해서 푸는 문제이다.
2. 코드
import sys
from collections import deque
input = sys.stdin.readline
if __name__ == "__main__":
n, m = map(int, input().split())
subSequenceList = [[] for _ in range(n + 1)] # 내 뒤에 오는 애들
degree = [0] * (n + 1) # 내 앞에 몇개 필요한지
dq = deque()
ans = []
for _ in range(m):
a, b = map(int, input().split())
subSequenceList[a].append(b)
degree[b] += 1
for i in range(1, n + 1):
if degree[i] == 0:
dq.append(i)
while dq:
prior = dq.popleft()
ans.append(prior)
for sub in subSequenceList[prior]:
degree[sub] -= 1
if degree[sub] == 0:
dq.append(sub)
print(*ans, sep=' ')