백준 1766 - 문제집(C++)

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

1766번: 문제집

위상정렬과 우선순위 큐를 이용한 문제입니다.

문제의 조건이 있습니다.

1. N개의 문제는 모두 풀어야 한다.

2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.

3. 가능하면 쉬운 문제부터 풀어야 한다.

   3-1. 문제 난이도는 문제 번호 순이다.

 

여기서 조건 2에 해당하지 않는 문제들이 있습니다. -> 관계가 형성되지 않는 문제들입니다.

그렇다면 관계가 형성되지 않는 문제들은 어떻게 처리해야 할까요? -> 조건 3을 통해 풀면 됩니다.

그렇다면 큐에 넣었을 때 문제 번호 순서에 따라서 정렬이 되야합니다 -> 우선순위 큐를 사용해야 합니다.(오름차순)

 

다시 한번 조건2에 대해서 생각해 보겠습니다. 

관계가 한번이 아닌 여려번 형성된 문제는 어떻게 해야하나?

예를 들어 (1 , 3) (2 , 3) (4 , 3) 으로 형성되어 있다고 하겠습니다. 그렇다면 이때 문제를 푸는 순서는 (1 , 2 , 4 , 3) 입니다.

여기서 문제의 관계 형성 수만큼 끝난 뒤에야 출력됨을 알 수 있습니다. -> 위상 정렬을 이용해야 합니다.

 

따라서 "위상 정렬을 base로 하면서 우선순위 큐를 통해 탐색 순서를 조정해주면 된다" 라는 결론을 내릴 수 있습니다.

 

위상 정렬을 푸는 방법은 X번이 몇번 방문했냐를 확인하는 것입니다.

예를 들어 (1 , 3) (2 , 3) (4 , 3) 이 있습니다. 그렇다면 3은 3번 방문해야 함을 알 수 있습니다. 따라서 배열을 통해 X번 수가 몇번 관계가 형성되었는지를 저장한 뒤, X번을 확인할 때마다 -1을 해주면서 0이 될 때까지 반복하면 됩니다.

3은 배열이 값이 3입니다.

1을 방문함으로서 3을 확인합니다 -> 이때 3의 배열 값이 2가 됩니다.

다시 2를 방문합니다. -> 3의 배열값이 1이 됩니다.

마지막으로 4를 방문합니다. -> 3의 배열 값이 0이 됩니다.

이때 배열 값이 0이 되었다면 해당 수를 방문할 수 있다는 의미가 됩니다. 따라서 이때 큐에 넣어주면 됩니다.

 

그렇다면 처음부터 배열의 값이 0이라면? -> 관계가 형성되지 않는 수라는 의미입니다. 따라서 큐에 넣어주고 시작하면 됩니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>

using namespace std;

int N, M;
vector<int> line[32001];
priority_queue<int, vector<int>, greater<int>> q;
int connect[32001];

void bfs() {
	while (!q.empty()) {
		int x = q.top();
		cout << x << " ";
		q.pop();
		for (int i = 0; i < line[x].size(); i++) {
			connect[line[x][i]]--;
			if (!connect[line[x][i]]) {
				q.push(line[x][i]);
			}
		}
	}
}

void solve() {
	for (int i = 1; i <= N; i++) {
		if (connect[i] == 0) q.push(i);
	}
	bfs();
}

int main() {
	cin.tie();
	cout.tie();
	cin >> N >> M;
	for (int i = 1; i <= M; i++) {
		int x, y;
		cin >> x >> y;
		line[x].push_back(y);
		connect[y]++;
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요