[백준] 2252 줄 세우기 (위상 정렬, topology sort)

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

2252번: 줄 세우기

 

위상정렬 (topology sort) 를 사용하면 쉽게 풀리는 문제이다.

위상정렬은 일의 우선순위가 있을 경우, 일을 처리하는 순서를 찾는 알고리즘이다.

답은 어떤 노드를 먼저 탐색하느냐에 따라 여러가지가 나올 수 있다.

 

위상정렬의 기본 구현 방법은

1. 진입차수를 저장해둔다.

2. 진입차수가 0 일 경우 queue 에 넣어준다. 

3. bfs 로 맵을 이동한다. 이동할때마다 진입차수를 -- 해주는 것을 잊지 말자.

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

int n,m;
vector <int> map[32001];
int input[32001];
vector <int> answer;
queue <int> q;

void topology() {

	while(!q.empty()) {
		int cur = q.front();
		q.pop();
		answer.push_back(cur);

		for(int i=0; i<map[cur].size(); i++) {
			int next = map[cur][i];
			if(--input[next] == 0) // 진입차수가 0 이 되면 넣어준다.
				q.push(next);
		}
	}
}

int main() {

	scanf("%d %d", &n, &m);

	for(int i=0; i<m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		input[b]++; // 진입차수
		map[a].push_back(b);
	}


	for(int i=1; i<=n; i++) {
		if(input[i] == 0) {
			q.push(i);
		}
	}
	topology();

	for(auto a: answer)
		printf("%d ", a);
}