Algorithm/알고리즘 종류1 위상 정렬 *** 위상정렬은 방향이 정해져있는 그래프에서 사용할 수 있다. (양방향 X) *** 1. 진입 차수가 0인 정점을 찾아 Queue에 넣는다. 2. Queue에서 정점 하나를 뺀후, 해당 정점에 연결된 간선을 제거한다. 3. 2번을 통해 간선이 제거된 정점이 진입차수가 0이라면 Queue에 추가한다. 4. 1번으로 다시 간다. V = 정점 E = 간선 시간 복잡도는 O(V+E) 만약 사이클이 있는 경우는 아래 그림과 같다 N = 6 일 경우 결과 배열에 총 6개가 아닌 [1, 6] 단 2개만 들어있을 것이다. 나머지는 진입 차수가 1보다 크기 때문에다. 아래는 배운 위상정렬로 풀 수 있는 문제이다. 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주.. 2022. 8. 5. 이전 1 다음
