자바생
Published 2021. 5. 28. 17:45
자바(백준) 9466 텀 프로젝트 BOJ(Java)
728x90

오답 노트 & 새로 알게 된 점

해당 문제를 이해하는 순간 제일 중요한 점 3가지를 깨달아야 한다.

  1. 노드들이 사이클을 이루는 순간 같은 팀이 됨
  2. 한 사람당 지목할 수 있는 팀원은 단 한 명
  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
profile

자바생

@자바생

틀린 부분이 있다면 댓글 부탁드립니다~😀

검색 태그