[c++] 백준 10451 - 순열 사이클(DFS)

0. [c++] 백준  -

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

1. 풀이

생각보다 너무 간단하게 풀려버렸다.

손으로 대충 끄적어보니 크기가 정해진 배열에서 각각 겹치지 않는 숫자를 가지는 경우에는 모두 루프를 가지게 된다. 이를 활용해서 문제를 해결하면 되는데, 탐색을 하며 이미 루프를 가진 숫자를 배제하는 방법을 구현하여 코드를 짜보았다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

#include<iostream> #include<cstring>   using namespace std;   int arr[1001]; bool visited[1001];   //아주 간단한 깊이탐색 구현 void DFS(int i) {     if (visited[i])         return;     visited[i] = true;     DFS(arr[i]); }   int findCycles(int N) {     //초기화를 해준다.     memset(visited, false, sizeof(visited));     int Count = 0;     for (int i = 1; i <= N; i++) {         //배열중에 아직 선택이 안된 것이 있다면,         if (!visited[i]) {             //깊이탐색을 해서 루프 고리를 찾아낸다.             DFS(i);             //그리고 루프 1개 추가.             Count++;         }     }       //루프 개수 반환     return Count; }   int main() {     int T, N;     cin >> T;     while (T--) {         cin >> N;         for (int i = 1; i <= N; i++) {             cin >> arr[i];         }         //루프를 찾으러 갑시다.         cout << findCycles(N) << endl;       } } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!