문제 출처 : https://www.acmicpc.net/problem/9466
9466번: 텀 프로젝트
문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 학생들이(s1, s2, ..., sr)이라 할 때, r=
www.acmicpc.net
이 문제는 싸이클을 찾아서 해결하는 문제이다.
방문 배열과 탐색 자체가 끝난 배열을 선언하여서 방문을 표시했다.
DFS 방법을 해서 사용방문을 못할 시에 싸이클을 탐색해서 문제를 해결 할 수 있었다.
아래는 해당 문제를 풀이한 소스 코드이다.
|
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
|
#include<stdio.h>
#pragma warning(disable:4996)
int N;
int arr[100001];
int visit[100001];
int finish[100001];
int cnt = 0;
void DFS(int n)
{
visit[n]++;
int temp = arr[n];
if (visit[temp] == 0)
DFS(temp);
if (finish[temp] == 0)
{
int i = temp;
while (1)
{
if (i == n)
break;
i = arr[i];
cnt++;
}
cnt++;
}
finish[n]++;
}
void reset()
{
for (int i = 1; i <= N; i++)
{
visit[i] = 0;
finish[i] = 0;
}
}
int main()
{
//freopen("test.inp", "r", stdin);
//freopen("test.out", "w", stdout);
int Test;
scanf("%d", &Test);
for (int i = 0; i < Test; i++)
{
scanf("%d", &N);
for (int j = 1; j <= N; j++)
scanf("%d", &arr[j]);
for (int j = 1; j <= N; j++)
{
if (visit[j] == 0)
DFS(j);
}
printf("%d\n", N - cnt);
cnt = 0;
reset();
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
'알고리즘' 카테고리의 다른 글
| 백준 2143번 문제 ( 두 배열의 합 ) (0) | 2020.07.03 |
|---|---|
| 백준 1753번 문제 ( 최단 경로 ) (0) | 2020.04.23 |
| 백준 1039번 문제 ( 교환 ) (0) | 2020.04.20 |
| 백준 2042번 문제 ( 구간 합 구하기 ) (0) | 2020.02.26 |
| 백준 5397번 문제 ( 키로거 ) (0) | 2020.02.26 |
뀨심볼
깃허브 주소는 : https://github.com/hhyc2 입니다~