[백준] 1766 문제집 (C++)

백준 1766 문제집

1. 문제

문제 링크

2. 접근법

[ 문제 접근 ]

 

위상 정렬을 사용하여 푸는 문제이며, 이전에 풀었던 2252번 줄 세우기 문제와 유사하다.

2021.12.18 - [알고리즘 스터디] - [백준] 2252 줄 세우기 (C++)

[백준] 2252 줄 세우기 (C++)

1. 위상정렬 문제는 진입 차수가 핵심이므로 indegree를 생성하여 다음 문제보다 먼저 풀어야 할 문제가 있다면 다음 문제를 기준으로 차수를 하나씩 증가시킨다. 

2. 또한 문제가 쉬운 난이도부터 먼저 풀어야 해서 우선순위 큐에 오름차순으로 정렬시켜야 한다.

3. 여기서는 위상 정렬을 BFS를 사용하여 풀었는데, 진입 차수가 0인 경우 pq에 먼저 넣어준다. 

4. 그리고 문제 수만큼 for문을 돌면서 큐가 비었다면 바로 리턴 시키고,

5. pq의 맨 앞에 있는 문제를 먼저 풀어야 할 문제로 택한 후 pop 시킨다. 

6. 이때 result 배열에 먼저 풀어야 할 문제를 넣어준다.

7. 다음으로 풀어야 할 문제를 정하기 위해 현재 문제 다음으로 풀 문제를 벡터에 담긴 수만큼 for문을 돌린다.

8. 다음 문제를 정하고 해당 문제의 차수를 1 감소시킨 후, 차수가 0이라면 pq에 담아준다.

9. 큐가 빌 때까지 위 과정을 반복한다. 

10. 이후 문제 수만큼 for문을 돌면서 result 벡터에 담긴 순서대로 출력해주면 된다. 

3. 코드

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

using namespace std;

int N, M;
vector<int> v[32001];
int result[32001], indegree[32001];
void topologySort()
{
	priority_queue<int, vector<int>, greater<int>> pq;
	//진입차수가 0인 경우 pq에 먼저 넣어줌
	for (int i = 1; i <= N; ++i)
	{
		if (indegree[i] == 0)
			pq.push(i);
	}
	//문제 수 만큼 for문 돌면서 먼저 풀어야 할 문제 처리해 줌
	for (int i = 1; i <= N; ++i)
	{
		if (pq.empty())
			return;
		int curr = pq.top();
		pq.pop();
		result[i] = curr;
		//현재 풀어야 할 문제의 다음 문제 정함
		for (int j = 0; j < v[curr].size(); ++j)
		{
			int next = v[curr][j];
			indegree[next]--;
			if (indegree[next] == 0)
				pq.push(next);
		}
	}
	//순서대로 출력
	for (int i = 1; i <= N; ++i)
	{
		cout << result[i] << " ";
	}
	cout << "\n";
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> M;
	for (int i = 0; i < M; ++i)
	{
		int a, b;
		cin >> a >> b;
		indegree[b]++;
		v[a].push_back(b);
	}

	topologySort();
	return 0;
}

4. 시간 복잡도

인접 리스트를 이용한 방법이므로 O(V+E)의 시간 복잡도를 가진다.

5. 결과