Easy is Perfect

[백준] 10451번 C/C++ 풀이 _ 순열 사이클

  • melonicedlatte
  • Feb 23, 2018


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

순열 사이클 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초256 MB38092431181163.745%

문제

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)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.

출력

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

예제 입력 

2
8
3 2 7 8 1 4 5 6
10
2 1 3 4 5 6 7 9 10 8

예제 출력 

3
7

힌트

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2014 F번

>> 풀이 방법

노드 구조체를 생성해주고, 모든 노드를 순회하면서 먼저 모든 노드를 전부 연결해준다. 
그 다음 같은 싸이클을 판단하는데, while 문을 통하여 시작점과 끝값이 같을 때 까지 next_node를 변경하면서 
싸이클 숫자를 세고 출력한다. 

시간 복잡도는 선형 탐색만 사용되기 때문에 O(N) 이다. 


>> 소스코드 

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <vector>
 
using namespace std;
 
vector<int> num_vec;
int* visited;
 
typedef struct NODE {
    int value;
    NODE* next_node;
}NODE;
 
void makeCycle(NODE** node_arr, int node_arr_size) {
    // 노드들 연결 
    for (int i = 1; i <= node_arr_size; i++) {
        node_arr[i]->next_node = node_arr[num_vec[i - 1]];
    } 
}
 
int getCycleNum(NODE** node_arr, int node_arr_size) {
    int cycleNum = 0; 
    for (int i = 1; i <= node_arr_size; i++) {
        // visited가 = 이면 싸이클 갯수를 늘려준다. 
        if (visited[i] == 0) {
            visited[i] = 1;
            cycleNum++;
            NODE* sub_node = node_arr[i]->next_node; 
 
            // 다음 노드값과 시작 노드 값이 같을때까지 수행
            while (  (node_arr[i]->value) != (sub_node->value)  ) { 
                visited[sub_node->value] = 1;
                visited[((sub_node->next_node)->value)] = 1; 
                sub_node = sub_node->next_node;
            } 
        }
        else {
            continue;
        }
    }
 
    return cycleNum;
}
 
 
int main() {
    int test_case;
    cin >> test_case;
 
    for (int k = 0; k < test_case; k++) {
        int one_case;
        NODE** node_arr;
 
        cin >> one_case;
 
        num_vec.clear();
        int sub;
        // 숫자 차례대로 받아오기 
        for (int i = 0; i < one_case; i++) {
            cin >> sub;
            num_vec.push_back(sub);
        }
 
        // n+1 개를 할당하고 0번째 인덱스는 버린다. 
        // 노드를 동적 생성한다. 
        node_arr = (NODE**)malloc(sizeof(NODE*)*(one_case + 1));
        for (int i = 1; i <= one_case; i++) {
            node_arr[i] = (NODE*)malloc(sizeof(NODE));
            node_arr[i]->value = i;
            node_arr[i]->next_node = NULL;
        }
        // visited 초기화 
        visited = (int*)malloc(sizeof(int)*(one_case + 1));
        for (int i = 1; i <= one_case; i++) {
            visited[i] = 0;
        } 
 
        // 사이클 만들기 
        makeCycle(node_arr, one_case);
        // 사이클 개수 얻기 
        cout << getCycleNum(node_arr, one_case) << "\n";
 
        delete node_arr;
        delete visited;
    }
 
    return 0; 
}
cs



Search