[G3] 백준 2252번 줄 세우기 C++ 위상 정렬

리뷰

 

위상 정렬의 가장 기본이 되는 문제

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

 

문제 풀이

1. n, m과 정수형 벡터 path를 n의 최대 크기인 32001로 전역 변수로 초기화 해준다.
2. input 함수를 통해 n, m값을 받고 m개의 키 정보를 받아 path 벡터에 연결 리스트를 추가해 준다.
3. solution 함수를 통해 위상 정렬을 수행해 준다, 정수형 벡터 cnt를 n + 1크기, 0으로 초기화 result를 초기화 해준다.
4. 1 ~ n을 탐색하여 i번째 path를 탐색하여 인접리스트에 저장된 노드의 cnt를 늘려준다.
5. 정수형 큐 q를 초기화 하고 1 ~ n을 탐색하여 만약 cnt가 0인 키 정보가 있다면 큐에 추가해 준다.
6. 큐가 빌때까지 while 루프를 돌며 현재 키를 result에 추가해 주고, 해당 키의 인접리스트의 cnt값을 1씩 줄여준다.
7. 인접리스트에 존재하는 키의 cnt가 0이 되었다면 해당 키 정보를 큐에 추가해 준다.
8. result 벡터의 크기가 n과 동일하다면 result 벡터를 리턴해 주고 해당 벡터 내 요소를 순차 출력한다.

 

참고 사항

초기에 cnt가 0인 키 정보는 정렬의 시작점이 되는 키 정보이다, 항상 키가 제일 큰 경우로 보면 된다.

cnt가 1이상인 경우 후순위에 있는 키 정보로 선 순위의 인접 리스트 탐색을 통해 cnt를 줄여지는 식으로 탐색한다.

문제에 따로 명시되어 있지 않기에 아마 result가 n과 동일하지 않은 케이스는 없을 것으로 보인다.

 

정답 코드

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

using namespace std;

int n, m;
vector<int> path[32001];

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

vector<int> solution() {
	vector<int> cnt(n + 1, 0);
	vector<int> result;
	for (int i = 1; i <= n; i++) {
		for (int node : path[i]) cnt[node]++;
	}

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

	while (!q.empty()) {
		int node = q.front(); q.pop();
		result.push_back(node);
		for (int next : path[node]) {
			if (--cnt[next] == 0) q.push(next);
		}
	}

	if (result.size() == n) {
		return result;
	}
	else return {};
}

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

	input();
	vector<int> ans = solution();
	for (int s : ans) cout << s << " ";
}