[BOJ 13214 // C++] Swaps

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 13214번 문제인 Swaps이다.
문제는 아래 링크를 확인하자.

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

13214번: Swaps

X를 N 이하의 양의 정수의 부분집합 중 A[i]들의 집합과 B[i]들의 집합이 같게 하는 i들의 집합 중 minimal한(minimum이 아니다) 집합이라 하자. 이 때 이 X에 속한 인덱스들의 A[i]들을 B[i]와 같이 바꾸기 위해 총 (X의 원소의 개수) - 1회의 swap 연산이 필요하다는 점을 관찰할 수 있다.

 

이를 이용해 위와 같은 성질을 지닌 X의 개수를 구해 N에서 빼주는 것으로 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;
int arr[1000001];
int nxt[1000001];
bool visited[1000001];

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

	cin >> N;
	for (int i = 1; i <= N; i++) {
		int x; cin >> x;
		arr[x] = i;
	}

	for (int i = 1; i <= N; i++) {
		int x; cin >> x;
		nxt[arr[x]] = i;
	}

	int ans = N;
	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			int ii = i;
			while (!visited[ii]) {
				visited[ii] = 1;
				ii = nxt[ii];
			}
			ans--;
		}
	}

	cout << ans;
}