백준저지
[순열 사이클]https://www.acmicpc.net/problem/10451
• 이 문제는 몇 개의 사이클이 존재하는지를 출력해야 한다.
• 문제 이해는 쉽게 되었고 시간도 얼마 걸리지 않았다.
• 구현
- 먼저 입력 받은 정점의 개수 + 1만큼 int형 vector타입 vec변수와
- 방문 여부를 나타내는 visitArr배열을 선언했다. (index와 값을 맞추기 위함)
- j는 index를 나타내고 vec[j]는 정점에 연결된 다른 정점을 뜻함
- 21 line: 정점의 개수만큼 반복한다.
- 22 line: 선택된 정점이 방문되지 않았다면,
- 23 line: visit 변수를 선택된 정점(j)으로 초기화하고
- 24 line: 아래 내용을 반복하는데,
- 25 line: 선택된 정점을 방문하고(true로 초기화)
- 26 line: 선택된 정점과 연결된 정점이 같다면,
- 27 line: 사이클 수를 증가하고
- 28 line: while(1)문을 빠져나가고 for문을 실행한다.
- 29 line: 선택된 정점과 연결된 정점이 같지 않다면,
- 30 line: visit변수를 선택된 정점에 연결된 정점으로 초기화 한다.
#include <iostream> #include <vector> using namespace std; int main(void) { int num; cin >> num; for (int i = 0; i < num; i++) { int cnt; int cycleCnt = 0; cin >> cnt; vectorvec(cnt + 1, 0); bool * visitArr = (bool *)malloc(sizeof(bool)*(cnt + 1)); for (int j = 1; j < cnt + 1; j++) { cin >> vec[j]; visitArr[j] = false; } for (int j = 1; j < cnt + 1; j++) { if (visitArr[j] != true) { int visit = j; while (1) { visitArr[visit] = true; if (j == vec[visit]) { cycleCnt++; break; } else { visit = vec[visit]; } } } } cout << cycleCnt << endl; free(visitArr); } return 0; }
'Study with book > Algorithms' 카테고리의 다른 글
[백준]2xn 타일링2 (0) | 2016.12.23 |
---|---|
[백준]2xn 타일링 (0) | 2016.12.23 |
[백준]DFS와 BFS3 (0) | 2016.12.22 |
[백준]DFS와 BFS2 (0) | 2016.12.22 |
[백준]DFS와 BFS1 (0) | 2016.12.22 |