목록2026/03/02 (1)

chyam

[백준] 2252번, python - 줄 세우기 (위상 정렬)

위상정렬에 관한 개념을 정확히 알지 못해서 문제를 푸는 데 어려움이 있었다. 위상정렬이란 방향 그래프에서 모든 간선 방향을 지키면서 노드를 나열하는 것을 의미한다.단, 사이클이 없는 그래프에서만 가능하다!! 대표적인 알고리즘은 다음과 같다. 1. 모든 노드의 진입차수를 계산한다2. 진입 차수가 0인 노드들을 큐에 추가한다3. 큐에서 노드를 하나 꺼내서 해당 노드와 연결된 간선을 제거한다4. 간선을 제거하여 진입 차수가 0이되면 다시 큐에 추가한다5. 큐가 빌 때까지 반복한다. 여기서 진입 차수가 0이라는 것은 해당 노드보다 앞에 와야 할 노드가 없다는 뜻이다. from collections import dequen, m = map(int,input().split())graph = [[] for _ in ..
백준 2026. 3. 2. 15:28
이전 Prev 1 Next 다음