일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 |
- 자바
- 후기
- node.js
- 컴퓨터그래픽스
- MySQL
- 몰입캠프
- 우선순위큐
- glfw
- BFS
- 대전맛집
- 위상정렬
- 프래그먼트
- 몰입캠프후기
- computergraphics
- 어은동맛집
- 카이스트
- 알고리즘
- 타입스크립트
- 앱개발
- html
- 궁동
- 리사이클러뷰
- nodeJS
- 분리집합
- 백준
- DP
- 프로그래머스
- 카이스트맛집
- 자바스크립트
- 안드로이드스튜디오
- Today
- Total
소근소근
[백준 BOJ 1766 gold2 - 문제집] 위상정렬(topological sort) , 우선순위 큐(priority queue) C++ 본문
[백준 BOJ 1766 gold2 - 문제집] 위상정렬(topological sort) , 우선순위 큐(priority queue) C++
JJureng 2021. 12. 29. 17:40백준 문제집 1766
https://www.acmicpc.net/problem/1766
1766번: 문제집
첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주
www.acmicpc.net
1부터 N까지의 문제를 푸는 순서를 출력한다.
조건은 두가지다.
1. 되도록 쉬운 문제 먼저 푼다.(작은 숫자 문제 먼저 풀어야 한다)
2. 먼저 푸는 문제가 있으면 먼저 풀어야 한다. (두 문제 간에 우선순위가 있다.)
문제 간의 우선순위를 지키면서, 쉬운문제를 풀어야 한다.
1번조건을 충족하기 위해서 우선순위 큐를 사용하고, 2번 조건은 위상 정렬을 떠올려야 한다.
이 두개를 떠올렸다면 엄청 쉽게 풀 수 있는 문제였다
알고리즘 들을 때 위상정렬 다 배웠는데 처음에 문제보고는 아예 떠올리지를 못했다.....
진짜 멀었다 ㅎㅎ... 열심히 해야지 ,,
위상정렬 알고리즘
사이클이 없고, directed graph여야 한다. (DAG)
각 노드별로 들어오는 edge개수를 저장한다(indegree)
1. indegree[k] 가 0 인 노드를 queue에 넣는다. (이 문제의 경우에는 priority queue)
2. queue를 돌면서, top을 pop하고, top이 가리키는 edge를 다 삭제한다. (indegree가 0 이 되는 노드가 생기면 queue에 push한다.)
3. 반복...
cin >> N >> M;
for (int i = 1; i <= M; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
degree[b]++;
}
for (int i = 1; i <= N; i++) {
if (degree[i] == 0) {
pq.push(-i);
}
}
while (!pq.empty()) {
int top = -pq.top();
pq.pop();
cout << top << " ";
for (int i = 0; i < adj[top].size(); i++) {
int next = adj[top][i];
degree[next]--;
if (degree[next] == 0) {
pq.push(-next);
}
}
}
pq에 음수로 넣는 이유는 오름차순 정렬을 위해서이다.
'Algorithm' 카테고리의 다른 글
[백준 BOJ 2056 gold4 - 작업] 위상정렬(topological sort) C++ (0) | 2021.12.31 |
---|---|
[백준 BOJ 1516 gold3 - 게임 개발] 위상정렬(topological sort) C++ (0) | 2021.12.31 |
[백준 BOJ 1715 gold4 - 카드 정렬하기] priority queue(힙, 우선순위 큐 ) , c++ (0) | 2021.12.29 |
[백준 BOJ 11053 silver4 - 가장 긴 증가하는 부분 수열] Longest Incresing Subsequence (LIS) (0) | 2021.12.27 |
[백준 BOJ 2096 gold4 - 내려가기] sliding window, dynamic programming (0) | 2021.12.27 |