[백준/BOJ] 백준 25577번 : 열 정렬정렬 정

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

25577번: 열 정렬정렬 정

 

순열 사이클(순열 그래프) 문제로, 주어진 배열과 완전히 정렬된 이후 옮겨진 위치 관계를 그래프로 만들어 순열 그래프를 만들고, 각 위치에서 dfs 하며, 순열 그래프에서 생기는 각 사이클의 크기를 확인해서 해당 사이클을 정렬하는 최소 연산 횟수를 구해가는 방법으로 문제를 해결했다.

 

코드

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

int n;
vector<pair<int, int>> a;

//순열 사이클(순열 그래프)를 이용해서 문제를 해결

int adj[100005]; //순열 그래프
int visited[100005];
int result = 0;

int dfs(int here, int cnt) {

	visited[here] = 1;
	cnt++;

	int there = adj[here];

	//there가 이미 방문한 지점일때
	if (visited[there] == 1) {
		return cnt;
	}

	return dfs(there, cnt);
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;
	for (int i = 0; i < n; i++) {
		int input;
		cin >> input;
		a.push_back(make_pair(input, i));
	}

	sort(a.begin(), a.end());
	for (int i = 0; i < a.size(); i++) {
		int before_index = a[i].second;
		int after_index = i;

		//순열 그래프 생성
		adj[before_index] = after_index;
	}

	//순열 그래프에서 생기는 각각의 사이클들의 크기를 통해 문제를 해결
	for (int i = 0; i < n; i++) {
		if (visited[i] == 0) {
			result += (dfs(i, 0) - 1); //해당 사이클의 크기 -1이 해당 사이클을 정렬하는 최소 연산
		}
	}

	cout << result << "\n";

	return 0;
}