알고리즘/BOJ

백준 1766번 문제집

꾸준함. 2019. 9. 29. 03:13

문제 링크입니다: https://www.acmicpc.net/problem/1766

 

1766번: 문제집

첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주어진다. 이는 A번 문제는 B번 문제보다 먼저 푸는 것이 좋다는 의미이다. 항상 문제를 모두 풀 수 있는 경우만 입력으로 주어진다.

www.acmicpc.net

간단한 위상정렬 문제였습니다.

문제 번호 오름차순으로 쉬운 문제이므로 우선순위 큐를 통해 minHeap을 구성하는 것이 핵심이였습니다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
const int MAX = 32000 + 1;
int N, M;
int inDegree[MAX];
vector<int> graph[MAX];
priority_queue<int, vector<int>, greater<int>> pq;
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for (int i = 0; i < M; i++)
{
int a, b;
cin >> a >> b;
inDegree[b]++;
graph[a].push_back(b);
}
for (int i = 1; i <= N; i++)
{
if (inDegree[i] == 0)
{
pq.push(i);
}
}
while (!pq.empty())
{
int node = pq.top();
pq.pop();
cout << node << " ";
for (int i = 0; i < graph[node].size(); i++)
{
int nextNode = graph[node][i];
if (--inDegree[nextNode] == 0)
{
pq.push(nextNode);
}
}
}
cout << "\n";
return 0;
}
view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

반응형

'알고리즘 > BOJ' 카테고리의 다른 글

백준 6118번 숨바꼭질  (0) 2019.09.29
백준 1516번 게임 개발  (0) 2019.09.29
백준 16674번 2018년을 되돌아보며  (0) 2019.09.25
백준 2842번 집배원 한상덕  (0) 2019.09.21
백준 3649번 로봇 프로젝트  (0) 2019.09.21