topological sort2 BOJ 1948 - 임계영역(그래프, 위상정렬) https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net - 문제에서 2가지를 요구하는데 하나는 DAG가 주어지고 시작노드부터 끝노드까지 가야하는데 여기서 가장 긴 경로를 찾는 것, 다른 하나는 그 경로에 포함된 엣지의 갯수를 찾는 것이다. * 위상정렬 구현 방식(bfs로 구현할 때) - dfs나 스택도 가능함 1. 각 노드들의 진입 차수 계산 2. 진입 차수가 0인 노드들을 큐에 삽입 3. 큐에서 노드를 꺼내 연결된 간선을 .. 2021. 8. 20. [boj] 2056 - 작업 C++ 풀이(DAG, BFS) www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 작업의 선행관계가 주어졌을 때, 모두 마치는 가장 빠른 시간을 구하는 문제이다. 전형적인 DAG문제이고, 위상정렬 로직을 bfs로 구현해서 모든 노드를 순서대로 순회했을 때의 최종 시간을 구하면 된다. #include #include #include #include using namespace std; int n; vector graph[10001]; vector ind(10001); // indegr.. 2021. 3. 28. 이전 1 다음
