728x90
오답 노트 & 새로 알게 된 점
해당 문제를 이해하는 순간 제일 중요한 점 3가지를 깨달아야 한다.
- 노드들이 사이클을 이루는 순간 같은 팀이 됨
- 한 사람당 지목할 수 있는 팀원은 단 한 명
- 자기 자신을 선택할 경우 바로 처리해주기
ex)
1 -> 3
2 -> 1
3 -> 3
4 -> 7
5 -> 3
6 -> 4
7 -> 6
지나왔던 경로(팀원 수를 구하기 위해)를 알기 위해 순서가 보장되고 동적인 ArrayList를 사용하였다.
4 -> 7 -> 6 -> 4로 사이클이 이루어질 때, ArrayList에는 4, 7, 6이 저장되어있다. 그래서 재방문한 값의 index 위치를 찾아 해당 위치부터 ArrayList.size()까지 빼주면 지나왔던 경로들의 개수를 알 수 있다. 그래서 result값에서 해당 count값을 빼주면 된다.
코드
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
|
package DFS;
import java.io.*;
import java.util.*;
public class Main {
static ArrayList<Integer>[] arr;
static boolean visit[];
static int nV, count;
static ArrayList<Integer> al;
public static void main(String[] a) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int test = Integer.parseInt(st.nextToken());
while(test -- > 0) {
st = new StringTokenizer(br.readLine());
nV = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
arr = new ArrayList[nV+1];
visit = new boolean[nV+1];
int result = nV;
for(int i = 1; i < nV+1; i++){
arr[i] = new ArrayList<>();
}
for(int i = 1; i < nV+1; i++) {
int j = Integer.parseInt(st.nextToken());
arr[i].add(j);
//자기 자신을 선택할 경우에
//바로 팀이 구성되기 때문에 result값에서 1을 빼줌
if (i == j) {
result -= 1;
visit[i] = true;
}
}
for(int i = 1; i < nV + 1; i++) {
if (!visit[i]) {
count = 0;
al = new ArrayList<>();
//방문 한 경우가 없을 경우 dfs를 돌림
dfs(i);
result -= count;
}
}
System.out.println(result);
}
}
static void dfs(int num){
//방문했는데 또 방문할 경우
//ArrayList를 사용하여 다시 방문한 곳 ~ 끝까지 index의 개수를 구함
//그래야지 팀이 몇명으로 이루어지는지 알 수 있음
if(visit[num]){
for(int i = 0; i < al.size(); i++){
if(al.get(i) == num) {
count = al.size() - i;
return;
}
}
}
else {
visit[num] = true;
al.add(num);
int next = arr[num].get(0);
dfs(next);
}
}
}
|
cs |
728x90
'BOJ(Java)' 카테고리의 다른 글
자바(백준) 2583 영역 구하기 (0) | 2021.05.28 |
---|---|
자바(백준) 21772 가희의 고구마 먹방 (0) | 2021.05.28 |
자바(백준) 2636 치즈 (0) | 2021.05.27 |
자바(백준) 11047 동전 0 (0) | 2021.05.22 |
자바(백준) 2206 벽 부수고 이동하기 (0) | 2021.05.17 |