문제링크 : https://www.acmicpc.net/problem/1766
이 문제는 "우선순위 큐"를 사용한 "위상정렬" 이다.
위상정렬은, 어느 순서를 지키면서 정렬해가는 방법이다.
스타크래프트에서의 빌드 같은 거라고들 한다.
위상정렬을 푸는 방법은
1. DFS 이용
2. InDegree 이용
두가지 방법이 있다고 한다.
DFS의 경우, DFS하였을 때 종점부터 하나씩 스택에 넣고 전부 탈출시 스택에있는것을 꺼내기만 하면 된다고 한다.
Indegree의 경우(들어오는 간선) 들어오는 간선의 개수가 0인것을 모두 큐에 넣으면 되고, 정점의 개수만큼 반복문을 도는데, 돌때마다 큐의 맨 앞 원소를 꺼내어 그 원소와 연결된 간선을 모두 지워주고,( 연결된 상대 정점의 indegree는 하나씩 감소하게 된다) 또 indegree가 0인것을 큐에 넣어주고,.. 하면 되는 문제이다.
이 문제에서는 Indegree를 이용하여 해결하였다. 위상정렬의 개념을 모르고 4시간가량 열심히 풀었는데, 위상정렬의 개념을 알고 나니 10분이면 풀린 문제였다.
소스코드 :
이 문제는 "우선순위 큐"를 사용한 "위상정렬" 이다.
위상정렬은, 어느 순서를 지키면서 정렬해가는 방법이다.
스타크래프트에서의 빌드 같은 거라고들 한다.
위상정렬을 푸는 방법은
1. DFS 이용
2. InDegree 이용
두가지 방법이 있다고 한다.
DFS의 경우, DFS하였을 때 종점부터 하나씩 스택에 넣고 전부 탈출시 스택에있는것을 꺼내기만 하면 된다고 한다.
Indegree의 경우(들어오는 간선) 들어오는 간선의 개수가 0인것을 모두 큐에 넣으면 되고, 정점의 개수만큼 반복문을 도는데, 돌때마다 큐의 맨 앞 원소를 꺼내어 그 원소와 연결된 간선을 모두 지워주고,( 연결된 상대 정점의 indegree는 하나씩 감소하게 된다) 또 indegree가 0인것을 큐에 넣어주고,.. 하면 되는 문제이다.
이 문제에서는 Indegree를 이용하여 해결하였다. 위상정렬의 개념을 모르고 4시간가량 열심히 풀었는데, 위상정렬의 개념을 알고 나니 10분이면 풀린 문제였다.
소스코드 :
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
31
32
33
34
35
36
37
38
39
40
41
|
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <queue>
using namespace std;
int main(void){
int n, m;
cin >> n >> m;
vector< priority_queue< int, vector<int>, greater<int> > > pq(n + 1);
vector<int> inDegree(n + 1);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
pq[a].push(b);
inDegree[b]++;
}
priority_queue< int, vector<int>, greater<int> > q;
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
for (int i = 1; i <= n; i++) {
int front = q.top();
cout << front << ' ';
q.pop();
while (!pq[front].empty()) {
inDegree[pq[front].top()]--;
if (inDegree[pq[front].top()] <= 0) {
q.push(pq[front].top());
}
pq[front].pop();
}
}
}
| cs |
댓글
댓글 쓰기