[백준] 10451번 순열 사이클

문제

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 (1234567832781456) 와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

순열을 배열을 이용해 (1…i…nπ1…πi…πn) 로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.

Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.

출력

각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.

 

처음 이 문제를 접근했을때, bfs로 풀려고 시도 했다. 하지만 끝내 풀지 못하고 다른 블로그를 참조한끝에 dfs로 바꾸게 되었다. 사실 dfs를 쓰지 않으려고하는 이유가 bfs의 장점중 하나가 dfs보다 빠른 시간내에 찾는다는 게 좋았다. 물론 실질적인 시간은 같을 수 있겠지만...뭐랄까... 찾는 로직이라고 해야하나 그런게 더 좋다는 것 같다.

 

그런데 이 문제는 최소문제가 아닌데 bfs로 풀려고 했다. 더 간단한 dfs가 있는데 굳이 bfs로 풀려고 했을까?

이 문제에서 제일 주목해야하는 점은 temp없이 swap을 시키는 것이 가장 중요하다. 다른것도 중요하긴 하지만,

이 문제를 풀기 위해서는 반드시 알아야 한다.

 

#include <bits/stdc++.h>
using namespace std;
int n;
int dist[1010];
bool visit[1010];

void dfs(int node) {
  visit[node] = true;
  if (!visit[dist[node]]) {
    dfs(dist[node]);
  }
}
int main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);

  cin >> n;
  memset(visit,false,sizeof(visit));
  for(int i = 1;i<=n;i++) {
    cin >> dist[i];
  }
  int ans = 0;
  for(int i = 1;i<=n;i++) {
    if (!visit[i]) {
      dfs(i);
      ans++;
    }
  }
  cout << ans <<  "\n";

}

일부러 tc는 뺏다. 설명하기 애매해서ㅎㅎ

아무튼

이 코드에는 변수없이 swap시키는 부분이 2개나 있는데

제일 위부터 살펴보면 visit[dist[node]] 이게 왜 swap이라고 말하는지 의문을 가진 사람들도 존재할지도 모른다.

 

예제를 보면

1 2 3 4 5 6 7 8

3 2 7 8 1 4 5 6 이렇게 나온다.

 

그러면 1-> 3 -> 7 -> 5 -> 1 이런식으로 동작하는데

이걸 넣어보자. (방문 조건은 생략한다.)

dfs(1) -> dfs(dist[1]) -> dfs(3) -> dfs(dist[3]) -> dfs(7) -> dfs(dist[7]) -> dfs(5) -> dfs(dist[5]) -> dfs(1)

뭐 이런식으로 된다. 이런게 가능한 이유는

인덱스 번호때문에 가능한거라 생각한다.

 

이제 dfs랑 이 방법도 적극적으로 활용해야지!

 

#include <stdio.h>
int calculate(int N, int* arr) {
	bool isVisited[1004] = { false, };
	int cnt = 0;
	for (int st = 1; st <= N; st++) {
		if (isVisited[st])
			continue;
		cnt++;
		isVisited[st] = true;
		int nxt = arr[st];
		while (nxt != st) {
			isVisited[nxt] = true;
			nxt = arr[nxt];
		}
	}
	return cnt;
}
int main(void) {
	int T;
	scanf("%d", &T);
	while (T--) {
		int N;
		scanf("%d", &N);
		int arr[1002];
		for (int i = 1; i <= N; i++)
			scanf("%d", &arr[i]);
		printf("%d\n", calculate(N, arr));
	}
}

봐 스왑시키잖아... 

하나 배웠다.!