[백준] [C++] 순열 (dfs, 순환)

1. 문제

 

1115번: 순열 (acmicpc.net)

1115번: 순열

 

완벽한 순열 == 순열이 해당 규칙에의해 모든 정점을 방문하는 순환형태

P와 Q의 차이 == P[i] 와 Q[i]의 값이 다른 i 의 개수

 

이 문제에서 주어진 규칙에 의해 주어진 순열은 한 정점당 한 엣지를 가지는 방향그래프로 생각할 수 있으며,

이는 곧 그래프 문제로 변형하여 문제를 해결 할 수 있음을 의미한다. 

 

2. 차이가 가장 작은 완벽한 순열 찾기

 

 

주어진 그래프가 위와 같다 해보자

0	1	2	3	4
1	2	0	4	3

 

이 그래프에서 두 정점의 위치를 서로 바꾸면 완벽한 순환을 만들어 낼 수 있다.

0	1	2	3	4
1	2	3	4	0

 

이러한 성질이 있음을 발견하게되면

 

'차이'는 순환하는 구간의 개수가 된다는 것을 알 수 있다.

 

 

 

3. 순환 찾기

 

순환을 찾는 가장 보편적인 방법은 dfs를 돌려 방문했던곳을 다시 방문하는지 체크하는 것이다.

 

이 문제는 엣지가 1개이므로 간단하게 구현할 수 있다.

 

#include <iostream>
#include <vector>
 
using namespace std;
 
void dfs(int here, vector<int>& a, vector<bool>& visited) {
    if(visited[here]) return;
    visited[here] = true;
    dfs(a[here], a, visited);
}
 
void dfsAll(vector<int>& a) {
    int count = 0;
    vector<bool> visited(a.size(), false);
    for(int i = 0; i < a.size(); i++) {
        if(!visited[i]) {
           dfs(i, a, visited);
           count++;
        }
    }
    cout<<((count == 1)? 0 : count) <<"\n";
}
 
int main() {
    vector<int> a;
    int n = 0;
    cin>>n;
    for(int i = 0; i < n ; i++) {
        int tmp = 0;
        cin>>tmp;
        a.push_back(tmp);
    }
    dfsAll(a);
}