[C/C++] 코드업(codeup) 3212번 위상 정렬(topological sort)

▽문제 바로가기

https://codeup.kr/problem.php?id=3212

위상 정렬(topological sort)

---

입력

첫째 줄에 정점의 개수 v (2 <= v <= 200)와 간선의 개수 n(1<=n<=700)이 입력된다. (만약, v가 6이라면 정점번호는 1~6)

둘째 줄 부터 간선의 정보 (a, b)가 쌍으로 입력된다. (a → b를 의미)

 

출력

위상 정렬의 결과를 출력한다. 

우선 순위가 같을 땐 정점의 번호가 낮은 것을 우선으로 한다.

사이클이 존재하여 위상정렬을 할 수 없다면 -1을 출력한다.

 

문제 풀이

 

위상 정렬에 대해서 잘 몰랐는데 아래 블로그에 잘 정리되어있어서 배웠습니다.

 

https://jason9319.tistory.com/93

Topological Sort(위상 정렬)

큐와 DFS로 하는 두 가지 방법이 있습니다.

 

이 문제의 경우 우선순위가 같을 땐 정점의 번호가 낮은 것을 우선으로 한다고 명시되어있기에 큐로 구현할 시 우선순위 큐를 사용하면 좋습니다.

 

구현 과정은 다음과 같습니다.

 

1. 입력받을때 정점과 간선을 연결해준다. 동시에 차수를 올려준다.

- 정점과 간선연결은 벡터에 push 하면 되겠죠? 차수 계산은 차수를 저장할 벡터나 배열을 따로 만들어서 계산해줍니다.

2. 처음에 차수가 0인정점을 찾는다.(두 개 이상일 수도 있음)

- 차수를 저장한 벡터나 배열을 탐색하여 0인 정점을 우선순위큐에 저장합니다.

3. 큐에서 pop합니다.

- 큐에서 pop 하고 방문처리를 합니다. 방문처리는 사이클 여부를 확인하기 위해서입니다.

4. pop 한 정점과 연결된 간선을 제거합니다.

- pop한 정점과 연결된 정점의 차수를 1 내립니다.

5. 차수가 0인 정점들을 큐에 넣습니다.

- 이때 우선순위 큐는 자동으로 정렬해줍니다.

6. 3번 4번 5번 과정을 반복합니다.

- 차수가 0인 정점이 없으면 위상 정렬이 완료되었거나 사이클이 존재합니다.

 

 

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

int main(){
	int v, n;
	scanf("%d%d", &v, &n);
	
	vector <int> vec[v+1];	//정점과 간선정보를 저장할 벡터
	int indegree[v+1]={0,};	//정점의 indegree(차수)를 저장할 벡터
	int a, b;
	for(int i=0;i<n;i++){
		scanf("%d%d", &a, &b);
		vec[a].push_back(b);	//연결
		indegree[b]++;	//차수올림
	}
	
	priority_queue <int, vector<int>, greater<int> > q;
	queue <int> printQ;	//출력용 큐
	bool visit[v+1] = {false,};	//방문체크, 싸이클 존재여부판단
	
	//처음 차수가 0인정점 찾기
	for(int i=1;i<=v;i++){
		if(indegree[i]==0) q.push(i);
	}
	
	bool isCycle = false;
	while(!q.empty()){
		if(q.top()>=v+1) break;
		//큐에서 pop하고 방문처리
		int now = q.top();
		visit[now] = true;
		printQ.push(now);
		q.pop();
		//pop한 정점과 연결된 간선제거(차수내림)
		for(int i=0;i<vec[now].size();i++){
			if(visit[vec[now][i]]==true) {isCycle = true; break;}
			indegree[vec[now][i]]--;	//차수내림
			if(indegree[vec[now][i]]==0) {q.push(vec[now][i]);}	//차수가 0이면 큐에 넣음
		}
		if(isCycle) break;
	}
	
	//싸이클이 존재
	if(isCycle) printf("-1");
	else if(printQ.size()!=v) printf("-1");
	
	//싸이클이 존재하지 않음
	else{
		for(int i=0;!printQ.empty();i++){
			printf("%d\n", printQ.front());
			printQ.pop();
		}
	}
	
	return 0;
}