[G5] 백준 14567번 선수과목 (Prerequisite) C++ 위상 정렬

리뷰

 

https://www.acmicpc.net/problem/14567

까먹을까봐 간만에 풀어본 위상정렬 문제

 

 

전역 변수

• N : 배열의 최대값을 저장할 정수형 상수 변수
• n : 과목의 개수를 저장할 변수
• m : 선수 조건의 개수를 저장할 변수
• result : 각 과목이 최소 몇학기에 이수할 수 있는지 저장할 정수형 배열
• lst : 간선을 저장하기 위한 정수형 벡터 배열

 

함수

없음

 

 

문제풀이

1. n, m값을 입력 받고, m개의 간선 정보를 입력받아 lst배열에 저장한다.
2. 정수형 벡터 cnt를 n + 1크기로, 기본값은 0인 상태로 초기화 한다.
3. 1번 과목부터 순서대로 연결된 간선을 순회하며 다음 과목의 cnt를 증가시켜 준다.
4. 정수형 타입의 큐 q를 초기화 하고, 1번 과목부터 순회하며 cnt가 0인경우 q에 push해준다.
5. q가 빌 때 까지 while루프를 돌고, 각 루프마다 요소를 한개씩 빼내 정수형 변수 cur에 저장해 준다.
6. cur과목의 result배열의 값을 1만큼 증가시켜 준 후 해당 과목과 연결된 과목을 순회한다.
7. 연결된 과목의 cnt를 줄여주고, 만약 0이 되었다면 q에 해당 과목을 push해준다.
8. q에 push된 경우 해당 과목의 result배열의 값을 선수과목의 값과 현재 값중 큰 값으로 갱신해 준다.
9. while루프가 종료된 후 1번 과목부터 n번 과목까지 result에 저장된 값을 공백을 구분으로 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• max대신 if문을 통해 최대값을 갱신해 주었더니 시간이 4ms밖에 줄지 않았다.

 

정답 코드

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

const int N = 1001;
int n, m;
int result[N];
vector<int> lst[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	while (m--) {
		int a, b; cin >> a >> b;
		lst[a].push_back(b);
	}

	vector<int> cnt(n + 1, 0);
	for (int i = 1; i <= n; ++i) {
		for (int j : lst[i]) cnt[j]++;
	}

	queue<int> q;
	for (int i = 1; i <= n; ++i) {
		if (!cnt[i]) q.push(i);
	}

	while (!q.empty()) {
		int cur = q.front(); q.pop();
		result[cur]++;
		for (int i : lst[cur]) {
			if (!--cnt[i]) {
				q.push(i);
				if (result[i] < result[cur]) result[i] = result[cur];
			}
		}
	}

	for (int i = 1; i <= n; ++i) cout << result[i] << " ";
}