BOJ 31003 언젠가 정렬이 될 수 있으면 좋겠네.

문제 링크입니다.

관찰

두 인접한 원소가 서로소인 경우에 한해 순서를 바꿀 수 있습니다. 거꾸로 생각하면, 서로소가 아닌 원소가 튀어나오면 그 원소는 죽어도 앞지를 수 없다는 뜻이 됩니다.

수열의 맨 앞부터 순서대로 가능한 가장 작은 수를 가져다 채우는 것이 유리합니다. 이때 서로소가 아닌 원소를 일종의 칸막이처럼 생각하고, 그 칸막이들이 모두 자기 자리를 찾아가기 전까지는 뒤의 원소를 꺼낼 수 없는 것처럼 생각할 수 있습니다.

아무튼 정렬하기

모든 서로 다른 두 원소의 쌍에 대해, 만약 두 원소가 서로소가 아니라면 왼쪽의 원소에서 오른쪽의 원소로 가는 간선을 만들어 줍니다. 원소의 개수가 그리 많지 않으므로 실제로 각 원소 쌍의 최대공약수를 구해 가면서 처리해도 됩니다. 이제 어떤 원소를 수열에 넣으려면 먼저 그 원소로 들어가는 모든 간선에 붙은 원소들을 수열에 넣어야 합니다. 간선은 처음 수열의 왼쪽에서 오른쪽으로만 이어지기 때문에 일종의 DAG가 되고, 그렇기에 위상 정렬이 가능합니다.

원소들을 위상 정렬한 후에, 진입 차수가 0인 정점들을 우선순위 큐와 같이 정렬성을 유지하는 자료 구조로 관리하면서 왼쪽부터 가능한 제일 작은 수를 꺼내 채워주기를 반복하면 원하는 수열 $A$를 얻을 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<int>> e;
int deg[3030], a[3030];

int gcd(int a, int b){
	return a ? gcd(b%a, a) : b;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n; cin >> n; e.resize(n+1);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		for(int j = 1; j < i; j++){
			if(gcd(a[j], a[i]) != 1){
				e[j].push_back(i);
				deg[i]++;
			}
		}
	}
	priority_queue<pair<int, int>> pq;
	for(int i = 1; i <= n; i++) if(!deg[i]) pq.push({-a[i], i});
	while(pq.size()){
		int now = pq.top().second;
		pq.pop();
		cout << a[now] << ' ';
		for(auto nxt : e[now]){
			if(!(--deg[nxt])) pq.push({-a[nxt], nxt});
		}
	}
}