개발윗미

C++로 구현한 2252번 줄 세우기 문제 풀이입니다. https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net #include #include #include #define MAX 501 using namespace std; int n, inDegree[MAX], result[MAX], time[MAX]; vector a[MAX]; void topologySort() { queue q; for(int i=1; i

C++로 구현한 2252번 줄 세우기 문제 풀이입니다. https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net #include #include #include #define MAX 32001 using namespace std; int n, inDegree[MAX], result[MAX]; vector a[MAX]; void topologySort() { queue q; for(int i=1; i

위상 정렬은 순서가 정해져있는 작업을 차례대로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 주의할 점은 위상 정렬은 사이클이 발생하지 않는 방향 그래프 즉, DAG(Directed Acyclic Graph)에만 수행이 가능하다. 왜냐하면 위상 정렬은 기본적으로 시작점이 존재해야 하는데 사이클 그래프에서는 시작점부터 찾을 수 없기 때문이다. 위상 정렬을 수행하는 과정은 아래와 같다. 정점 1 2 3 4 5 6 7 진입차수 0 1 1 1 1 2 1 여기서 진입차수는 해당 정점에 들어오는 간선의 수이다. 즉, 정점6은 정점4와 정점5에서 간선이 들어오기 때문에 진입차수가 2이다. 또한, 정점1은 들어오는 간선이 없기 때문에 진입차수는 0이다. (1) 진입차수가 0인 정점1을 큐에 삽입한다..