백준 1115: 순열

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

1115번: 순열

 

풀이

순열 $A$를 $i \ \rightarrow \ A[i]$인 유향그래프처럼 생각해 봅시다. $A$에 $0\sim N-1$의 수가 모두 하나씩 들어가 있으므로 모든 노드들은 indegree와 outdegree가 각각 1이 됩니다. 따라서 이 그래프는 사이클로만 이루어지게 됩니다(증명은 귀류법으로 쉽게 할 수 있으므로 생략합니다). 이 사이클의 개수를 세어줌으로써 수정할 값 개수를 구할 수 있게 됩니다.

 

위 문제의 예제 입력 4로 예를 들어 보겠습니다.

예제 입력 4의 순열의 그래프 표현

여기서 사이클의 개수는 총 3개입니다(0은 혼자서 고리를 이룹니다). 이 그래프에서 간선을 살짝 수정하여 전체를 하나의 사이클로 만들 수 있는 방법을 찾아야 합니다. 당연히도, 사이클이 3개이기 때문에 이들을 모두 인접하게 할 수 있는 3개의 간선을 수정하면 됩니다. 예를 들어 $4 \rightarrow 1$을 $4\rightarrow 0$으로, $0\rightarrow 0$을 $0\rightarrow 2$로, $3\rightarrow 2$를 $3\rightarrow 1$로 바꿔봅시다.

2 5 3 1 0 4 (원래 순열과의 거리는 3)

위와 같이 하나의 사이클로 바꿀 수 있음을 확인했습니다.

 

그러나 사이클 개수가 1개일 때는 굳이 수정할 이유가 없으므로 답은 0개가 됩니다.

 

따라서 사이클 개수를 $cnt$라 하면, 답은 $cnt==1$이면 0, 나머지는 $cnt$입니다.

 

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[50], cnt;
bool visited[50];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i=0; i<n; i++) cin >> a[i];
    for(int i=0; i<n; i++) if(!visited[i]) {
        cnt++;
        visited[i]=1;
        for(int j=a[i]; j!=i; j=a[j]) visited[j]=1;
    }
    if(cnt==1) cout << 0;
    else cout << cnt;
}