문제 : https://www.acmicpc.net/problem/1766
위상정렬 , 그래프이론
● 위상정렬 + 추가조건이 붙은 문제로 자료구조 우선순위 큐를 이용하면 쉽게 해결할 수 있습니다.
● 입력을 받아 x문제와 y문제가 선행 조건이 x가 먼저 풀려야되면 x에서 y로 가는 방향 간선을 그려주고
y의 inDegree 값을 증가시킵니다.
● inDegree가 0이라는 뜻은 먼저 풀려야되는 문제가 없다는 뜻으로 지금 당장 풀어도 됩니다. 하지만, 우리는 풀어도 되는 문제 중 난이도가 작은(문제 번호가 작은) 문제를 먼저 풀어야되므로, 가장 작은 값에 우선 순위를 부여하는 우선순위 큐를 만들어 활용하면 됩니다.
● inDegree가 0인 문제들을 모두 우선순위 큐에 넣고 하나씩 뽑아가며(가장 번호가 작은 문제) 출력하고, 해당 문제랑 연결되어 있는 문제들의 inDegree 값을 갱신해줍니다. 다시 inDegree가 0이 되는 문제들을 우선순위 큐에 넣어가며 모든 문제들을 출력하면 됩니다.
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int N, M, inDegree[32001] = {};
vector<int> graph[32001] = {};
priority_queue<int, vector<int>, greater<int>> pq;
cin >> N >> M;
for (int i = 0, x, y; i < M; i++) {
cin >> x >> y;
graph[x].push_back(y);
inDegree[y]++;
}
for (int i = 1; i <= N; i++)
if (inDegree[i] == 0)
pq.push(i);
while (!pq.empty()) {
int cur = pq.top();
pq.pop();
for (int i = 0; i < graph[cur].size(); i++) {
inDegree[graph[cur][i]]--;
if (inDegree[graph[cur][i]] == 0)
pq.push(graph[cur][i]);
}
cout << cur << ' ';
}
return 0;
}
'Problem Solving > BOJ' 카테고리의 다른 글
| [BOJ] 1005 : ACM Craft - travelbeeee (0) | 2020.04.03 |
|---|---|
| [BOJ] 1516 : 게임 개발 - travelbeeee (0) | 2020.04.03 |
| [BOJ] 15666 : N 과 M (12) - travelbeeee (0) | 2020.04.02 |
| [BOJ] 2252 : 줄 세우기 - travelbeeee (0) | 2020.04.02 |
| [BOJ] 16137 : 견우와 직녀 - travelbeeee (0) | 2020.04.01 |
