[백준] 9466번 : 텀 프로젝트

9466번: 텀 프로젝트

# 문제

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

1

2

3

4

5

6

7

3

1

3

7

3

4

6

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

# 입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

# 출력

각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

# 예제 입력

2

7

3 1 3 7 3 4 6

8

1 2 3 4 5 6 7 8

# 예제 출력

3

0

---

[DFS + Queue + Set]

이 문제는 주어진 그래프에서 사이클(Cycle)을 이루지 못하는 정점들의 개수를 출력하는 문제이다. 사이클이란 특정 정점 V에서 인접한 정점들을 통해(혹은 자기자신을 통해) 다시 정점 V로 돌아오는 것을 뜻한다. 따라서 DFS 도중 사이클이 있는지 확인하려면 방문한 정점의 인접리스트에 출발 정점 V가 있는지 확인하면 된다.

 

Queue는 정점 V에서 시작해 V1, V2, V3, ... Vn 정점을 담고 있다. Set은 사이클이 생기면 같은 정점이 중복되어 들어오기 때문에 false가 반환되는 것을 이용해 사이클이 발생했다고 판단했다. 이렇게 한 이유는 Queue나 List 또는 Array에서 .contains()를 사용하는 것 보다 훨씬 빠르게 값을 포함하고 있는지 여부를 알 수 있기 때문이다.

실제로 시간 초과를 여러번 경험하다가 Set을 사용하고 AC를 받았다.

 

방문했는지 여부인 visit[] 배열과, 사이클을 이룬(팀을 이룬) 사람의 번호는 solo[] 배열에서 true값을 갖는다. 따라서 solo[]에서 false의 개수를 세어 출력하였다.

 

# Code </>

public class Main {

    static final int N = 100001;
    static Set<Integer> set;
    static Queue<Integer> q;
    static int[] list;
    static boolean[] solo, visit;
    static boolean flag;

    static void DFS(int next){

        visit[next] = true;
        q.add(next);
        set.add(next);

        int v = list[next];

        if(!set.add(v)) //값이 중복하게 있다면
            while(!q.isEmpty()) {
                if (q.peek() == v) { //그 값이 나올 때 까지 dequeue
                    flag = true;
                    break;
                }
                q.poll();
            }

        if(!visit[v])
            DFS(v);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        
        for(int i=0; i<t; i++){

            int n = Integer.parseInt(br.readLine());

            set = new HashSet<>();
            q = new LinkedList<>();
            
            solo = new boolean[N];
            visit = new boolean[N];
            list = new int[N];

            StringTokenizer st = new StringTokenizer(br.readLine());
            int j = 1;
            while(st.hasMoreTokens()){
                int num = Integer.parseInt(st.nextToken());
                
                /*
                아래 코드를 넣으면 더 빠르게 동작한다.
                if(num == j){
                    visit[j] = true;
                    solo[j] = true;
                }
                */
                
                list[j++] = num;
            }

            for(int a=1; a<=n; a++)
                if(!visit[a]) {
                    flag = false;
                    DFS(a);
                    if(flag)
                        while(!q.isEmpty())
                            solo[q.poll()] = true;
                            
                    q.clear();
                    set.clear();
                }

            int sum = 0;
            for(int a=1; a<=n; a++)
                if(!solo[a]) sum++;

            System.out.println(sum);
        }
    }
}

# 반례 cases

글 읽기 - 테스트 케이스 올려봅니다