728x90 반응형 위상정렬1 [백준] 2252번: 줄 세우기 - python https://www.acmicpc.net/problem/2252 DAG 위상정렬을 이용한 문제 degree에 차수를 저장하고, 0인 차수를 큐에 넣음으로써 시작된다. 그 후 큐를 뽑아내며 그와 연결된 그래프의 차수를 감소하며 0일 경우에 큐에 삽입하여 큐가 빌때까지 이 작업을 반복한다. 처음에 인접행렬로 구현했으나 메모리초과로 인접리스트로 구현하니 메모리문제가 해결되었다.from collections import dequeimport sysinput = sys.stdin.readlinen, m = map(int, input().split())degree = [0] * (n+1)arr = [[] for _ in range(n+1)]dq = deque()for _ in range(m): a, b = .. 2024. 5. 7. 이전 1 다음 728x90 반응형