위상정렬2 위상 정렬 *** 위상정렬은 방향이 정해져있는 그래프에서 사용할 수 있다. (양방향 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. 백준 임계경로 1948번 javascript 위상정렬을 사용하여 풀 수 있는 문제입니다. 다만 역발상이 필요합니다. 아래 그림과 같이 위상정렬 + 위상 정렬 반대가 경로 최대값(12) 이라면 해당 정점들 사이의 간선은 1분도 쉬지 않고 달려야 하는 간선입니다. const fs = require("fs"); const stdin = ( process.platform === "linux" ? fs.readFileSync("/dev/stdin").toString() : `7 9 1 2 4 1 3 2 1 4 3 2 6 3 2 7 5 3 5 1 4 6 4 5 6 2 6 7 5 1 7` ).split("\n"); const input = (() => { let line = 0; return () => stdin[line++]; })(); const N = +.. 2022. 8. 5. 이전 1 다음
