[G1] 백준 3665번 최종 순위 C++ 위상 정렬

리뷰

 

각 순위별 간선을 생성하고, 쿼리로 입력되는 노드간 간선을 반전시킨 후 위상 정렬을 수행하는 문제

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

 

전역 변수

• tc, n, m : 테스트 케이스의 개수 tc, 팀의 개수 n, 순위 변경 쿼리의 개수 m
• lst : 작년 순위 정보를 저장할 정수형 벡터
• cnt : 선순위의 개수를 저장할 정수형 벡터
• result : 금년 순위 정보를 저장할 정수형 벡터
• path : 인접 리스트를 저장할 정수형 2차원 벡터

 

함수

1. init

void init()

 

각 테스트 케이스마다 lst, cnt, result, path 벡터를 clear해주는 함수

 

2. input()

void input()

 

1. n값을 입력 받고 각 테스트 케이스 마다 lst, cnt, path의 크기를 n + 1로 초기화 해준다.
2. 각 순위의 팀 정보를 lst벡터에 입력 받아준다.
3. 1등 팀부터 n등 팀까지 인접 리스트를 path 벡터에 초기화 해준다.
4. m값을 입력 받고 m개의 쿼리문에 대한 질의를 처리해 준다.
5. a의 인접리스트에 b가 존재한다면 a에서 b를 삭제하고 b에 a를 추가해 준다.
6. 만약 존재하지 않는다면 b에서 a를 삭제하고 a에 b를 추가해 준다.

3. solution()

void solution()

 

1. 위상정렬을 수행하는 함수
2. 각 노드의 인접리스트를 참조하며 인접리스트에 들어있는 팀의 cnt를 증가시켜 준다.
3. 정수형 큐 q를 초기화 해주고, cnt가 0인 팀을 큐에 삽입해 준다.
4. 큐가 빌때까지 while문을 수행하며 큐에서 pop한 팀을 result에 추가해 준다.
5. 해당 팀의 인접리스트를 순회하며 인접리스트에 존재하는 팀의 cnt를 감소시켜 준다.
6. 만약 감소시킨 후의 해당 팀의 cnt가 0이라면 큐에 해당 팀을 추가해 준다.
7. 최종적으로 result의 size가 n과 동일하다면 result에 존재하는 팀 정보를 공백을 기준으로 출력해 준다.
8. 아니라면 IMPOSSIBLE을 출력해 주면 된다.

 

문제풀이

1. tc를 입력 받고 tc만큼의 반복문을 수행해 준다.
2. init함수를 통해 이전에 사용한 벡터들을 초기화 해준다.
3. input함수를 통해 값을 입력 받고 각 벡터를 초기화 해준다.
4. solution함수를 통해 위상 정렬을 수행하고 정답을 출력한다.

 

참고 사항

vector에 find 처리를 해주는게 시간이 오래 걸릴 줄 알았는데 생각보다 시간이 오래 걸리지는 않았다.

팀이 중복되는 경우는 없으므로 set등을 고려해 봐도 좋을 것 같다.

 

정답 코드

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

using namespace std;
int tc, n, m;
vector<int> lst;
vector<int> cnt;
vector<int> result;
vector<vector<int>> path;

void init() {
	lst.clear();
	cnt.clear();
	result.clear();
	path.clear();
}

void input() {
	cin >> n;
	lst.resize(n + 1);
	cnt.resize(n + 1, 0);
	path.resize(n + 1);
	for (int i = 1; i <= n; i++) cin >> lst[i];
	for (int i = 1; i < n; i++) {
		for (int j = i + 1; j <= n; j++) {
			path[lst[i]].push_back(lst[j]);
		}
	}
	cin >> m;
	while (m--) {
		int a, b; cin >> a >> b;
		auto it = find(path[a].begin(), path[a].end(), b);
		if (it != path[a].end()) {
			path[a].erase(it);
			path[b].push_back(a);
		}
		else {
			auto it = find(path[b].begin(), path[b].end(), a);
			path[b].erase(it);
			path[a].push_back(b);
		}
	}
}

void solution() {
	for (int i = 1; i <= n; i++) {
		for (int j : path[lst[i]]) cnt[j]++;
	}

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

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

	if (result.size() == n) {
		for (int i : result) cout << i << " ";
		cout << "\n";
	}
	else cout << "IMPOSSIBLE\n";
}

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

	cin >> tc;
	while (tc--) {
		init();
		input();
		solution();
	}
}