문제 링크입니다: 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을 구성하는 것이 핵심이였습니다.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |


개발환경: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 |