ALGORITHM/BOJ
[백준] 9466 텀 프로젝트
0298
2020. 12. 1. 23:29
9466번: 텀 프로젝트
이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을
www.acmicpc.net
2020-12-01
|
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
|
import java.util.Scanner;
public class Main9466 {
public static int answer, N, arr[];
public static boolean vtd[], check[];
public static void solve(int num) {
vtd[num] = true;
int next = arr[num]; // next value
if(!vtd[next]) { // never visited
solve(next);
} else if (!check[next]) { // visited && not chekced?
for(int i = next; i != num; i = arr[i]) {
answer++;
}
answer++;
}
check[num] = true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int test = sc.nextInt();
for(int ts = 1; ts <= test; ts++) {
N = sc.nextInt();
arr = new int[N+1];
vtd = new boolean[N+1];
check = new boolean[N+1];
answer = 0;
for(int i = 1; i <= N; i++) {
int x = sc.nextInt();
arr[i] = x;
}
for(int i = 1; i <= N; i++) {
if(!vtd[i]) solve(i);
}
System.out.println(N-answer);
}
}
}
|
cs |
# 문제 요약
- 팀원 수에는 제한이 없다 (S1 -> S1 도 가능)
- 2 <= N <= 100,000
- S1 -> S2 -> S3 -> .... -> Sr -> S1 인 경우에만 팀으로 인정된다.
| 학생 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 선택 | 3 | 1 | 3 | 7 | 3 | 4 | 6 |
위와 같은 경우 (S3 -> S3) , (S4 -> S7 -> S6 -> S4) 두 경우를 제외하고는 팀을 만들 수 없다.
# 풀이
1. 입력
|
1
2
3
|
arr = new int[N + 1];
vtd = new boolean[N + 1];
check = new boolean[N + 1];
|
cs |
arr라는 int 배열은 각 학생별로 같이 프로젝트 하고 싶은 학생이 누구인지 정하게 된다.
vtd라는 boolean 배열은 방문한지 아닌지를 체크하게 된다.
check라는 boolean 배열은 다시 방문할 필요가 있는지 없는지를 체크하게 된다.
|
1
2
3
4
5
6
7
8
|
for(int i = 1; i <= N; i++) {
int x = sc.nextInt();
arr[i] = x;
}
for(int i = 1; i <= N; i++) {
if(!vtd[i]) solve(i);
}
|
cs |
1 부터 N 까지 하나씩 팀을 만들 수 있는지 없는지 체크한다. 이 때 방문한적이 없는 경우를 기준으로 체크하게 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public static void solve(int num) {
vtd[num] = true; // 함수를 부르면서 넘겨준 학생값(num)은 방문했다고 표시를 한다.
int next = arr[num]; // arr[num]은 그 학생(num)이 같이 하고 싶은 학생(next)의 넘버가 된다.
if (!vtd[next]) { // 만약 한번도 그 새로운 학생값(next)을 방문한적이 없다면,
solve(next); // 다시 한 번 학생값(next -> num)을 넘겨, 이 학생(new num)이 프로젝트를 같이 하고 싶은 학생값(new next)을 찾는다.
} else if (!check[next]) { // 만약 그렇게 넘겼던 값(next)이, 방문한적이 있으며(vtd[next] == true), 다시 방문해서는 안되는 값이 아닌 경우 (!check[next])
// 그 학생값(next)을 기준으로, 이 학생값(next)을 부른 다른 학생값(num)과 같아지기 전까지, 계속해서 연결된 다른 학생값(arr[num])을 부른다.
for (int i = next; i != num; i = arr[i]) {
answer++; //한 번 다른 학생을 부를 때마다, 팀원이 추가 되는 것이므로 answer값을 ++해준다
}
answer++; // 마지막으로 i == num 이 될 때 count를 못해주므로, 따로 count를 해준다. 또한 처음부터 next == num (Sx -> Sx)인 경우에도 count를 해준다.
}
check[num] = true; // 시작했던 num값은 check true로 바꿔줘서, 다시 갯수를 셀 때 체크하지 못하도록 한다.
}
|
cs |
마지막에 전체 N에서 answer만큼 빼주면, 팀을 만들지 못한 학생의 수를 구할 수 있다.
+) 계속 답이 이상하게 안 맞아서 결국 마지막에는 힌트를 얻었다. 결국 다른 사람들의 풀이를 찾아봤는데, 아무리 봐도 다른 블로그 풀이와 거의 유사했다. 아예 대놓고 코드 하나하나 비교해봤더니, 마지막 check하는 부분때문에 계속 틀린거였었다..