[1766] 문제집 - 위상정렬 ★★☆ / 복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/1766

1766번: 문제집

---

[ 문제 접근 ]

- 전형적인 위상 정렬 문제이다. 기본적인 풀이법만 알고 있으면 풀 수 있는 문제.

별 두개인  이유는 풀때 고민을 조금 했기 때문이다.

 

이유는 key point 에서.

---

[ 최종 코드 ]

#include<iostream>
#include<vector>
#include<queue>

using std::cout; using std::cin;
using std::vector;

int n, m;
vector<int> books[32001];
int indegree[32001];

void tS() {
	std::priority_queue<int,vector<int>,std::greater<int>> pq;  // pq는 작은 값이 top()에 존재하게끔.

	// 모든 책을 검색해 indegree가 0인 책을 찾아 pq에 넣어준다.
	for (int i = 1; i <= n; i++) {
		if (indegree[i] == 0) pq.push(i);
	}
	for (int j = 0; j < n; j++) { // 모든 책에 대해서
		int cur = pq.top();
		cout << cur << " ";
		pq.pop();
		for (auto elem : books[cur]) {
			if (--indegree[elem] == 0) {
				pq.push(elem);
			}
		}
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n >> m;
	int a, b;
	
	while (m--) {
		cin >> a >> b;
		books[a].push_back(b);
		indegree[b]++;
	}
	tS();
	return 0;
}

---

[ Key Point ]

 

👉 문제의 3번 조건 "가능하면 쉬운 문제부터 풀어야 한다." 때문에 내 풀의 방법으로는 풀 수 없었다.

그래서 DFS로 풀면 되지 않을까 하다가 문제 힌트를 조금 보니 Priority_queue가 써있는것을 보고 무릎을 딱 쳤다.

=> 아직 '이럴땐 이런 자료구조를 사용해야한다' 이런 개념이 많이 부족한것 같다. 막상 보면은 다 아는 자료구조인데 문제를 풀기만 하면 왜 그걸 사용해야된다는걸 모르는지..  문제 풀이가 부족하다. 많이 풀면 될것 같다.

---

[ 다른 사람 풀이 ]