반응형 위상 정렬2 BOJ 2252 : 줄 세우기 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2252 A가 학생 B 앞에 서야 한다는 조건이 있으므로 위상 정렬을 이용하여 풀면 된다. 즉, A → B에 대해 B의 indegree가 1 증가하고, indegree가 0인 학생부터 BFS를 시작하면 된다. 설명은 BOJ 1005 : ACM Craft와 동일하다. #include int N, M, A, B; int indegree[32100]; int queue[100100]; int rp, wp; typedef struct st { int value; struct st *next; }NODE; NODE HEAD[32100]; NODE POOL[100100]; int pcnt; void Make(int p, int c) .. 2021. 7. 17. BOJ 1005 : ACM Craft 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1005 위 그림에서 2번, 3번 건물은 1번 건물이 완료되어야 건설을 시작할 수 있다. 4번 건물은 2번, 3번 건물이 완료되어야 건설을 시작할 수 있다. 따라서 각 node에 들어오는 화살표 (in-degree)가 작은 순서대로 건설이 시작된다. 이런 문제는 위상 정렬을 이용해서 풀 수 있다. 1번의 경우에는 들어오는 화살표가 없으므로 in-degree가 0이다. 2, 3번의 경우는 in-degree가 1이며, 4번은 2가 된다. 입력받을 변수와 in-degree를 저장할 배열, 그리고 건설 시간을 저장할 배열, 답을 저장할 배열을 선언한다. ans[node] = 해당 node 건물이 완료될 때 까지 걸린 시간이다. #.. 2021. 7. 14. 이전 1 다음 반응형