[BOJ-9466] 텀 프로젝트(JAVA)

백준 9466 텀 프로젝트

 

9466번: 텀 프로젝트

 

 

문제 설명

 

 - 프로젝트 팀을 구하기 위해서 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다.

   (단 한 명만 선택할 수 있고, 자기 자신도 선택할 수 있다.)

 

 - 학생들이(S1, S2, S3, ... , Sr) 이라 할 떄 S1이 S1을 선택하는 경우나,

   S1이 S2를, S2가 S3를, .., Sr-1이 S1을 선택하는 경우 한 팀이 될 수 있다.

 

 - 예를 들어 아래와 같이 학생들이 선택을 했다고 가정해보자.

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

 

 

 - 주어진 선택의 결과를 보고, 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 구하라.

 

---

 

입력 값

 

 - 첫째 줄에 테스트 케이스의 개수 T가 주어진다.

 

 - 각 테스트 케이스의 첫 줄에는 학생의 수 n ( 2 <= n <= 100,000 )이 주어진다.

 

 - 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다.

   (모든 학생들은 1번부터 n번까지 번호가 부여된다.)

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 살펴보면 사이클이 존재하는 학생들은 팀을 이루는 것이고,

   그렇지 않은 학생들은 팀을 이루지 않게 되는 것이다.

 

 - 즉, 해당 학생이 사이클에 속해 있는지 판단하는 문제이다.

 

 - 간단하게 생각해보자면, 한 학생을 선택한 후 해당 학생을 시작으로 하여

   다시 그 학생으로 돌아오는지 판단하면 된다.

 

 - 다시 그 학생으로 돌아오는지 판단하는 방법은 DFS를 이용하면 된다.

   DFS를 이용하여 다른 노드 탐색 시 시작 학생이 다시 나오는지 판단하면 된다.

탐색 알고리즘 - 깊이 우선 탐색(Depth First Search, DFS)

 

 - 이러한 방법으로 하게 되면, 학생수 N이고, 각 학생들은 하나의 학생을 가르키기 때문에

   간선의 수도 N이 된다. 즉, 한 학생당 O(N)의 시간복잡도를 가지고 사이클에 속해 있는지 판단하게 된다.

 

 - 결론적으로 간단하게 생각한 방법은 O($N^2$)의 시간복잡도를 가지게 된다.

   다만, N의 최댓값은 10만이기 떄문에 각 테스트 케이스마다 100억의 시간이 소요된다.

   즉, 이 방법은 불가능하다.

 

 - 그렇다면 어떻게 해야 할까?

 

 - 중복 체크하는 학생들을 제거해야 한다.

 

 - 한 학생을 선택하여 그 학생과 연결된 모든 학생들을 탐색하면서 사이클이 있는지 판단한다.

 

 - 사이클이 존재한다면, 그 사이클 안에 있는 학생들은 사이클에 포함된 학생들이라 표시한다.

 

 - DFS를 돌면서 지났던 학생들은 다시 선택되어도 똑같은 결과를 가져오기 때문에 다시 방문하지 않도록 표시한다.

 

 - 정리하자면,

   1. 모든 학생들을 차례로 돌아가며 선택한다.

   2. 한 학생을 시작으로 DFS를 돌면서 사이클이 있는지 판단한다.

     (사이클 안에는 시작 학생이 포함되지 않을 수 있다.)

   3. 사이클에 포함된 학생들은 팀을 이루었다는 표시를 한다.

   4. 해당 DFS를 탐색하며 지났던 학생들을 따로 표시한다.

   5. DFS종료 후 다시 1번으로 돌아가고, 3번에 의해서 표시된 학생들인 경우 스킵한다.

     

 

 

---

 

 

소스 코드

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// https://www.acmicpc.net/problem/9466
// 텀 프로젝트
public class Main {

    private static int boards[] = new int[100001];
    private static boolean visited[] = new boolean[100001];
    private static boolean dfsVisited[] = new boolean[100001];
    private static int recNum=-1;
    private static int result=0;

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        StringBuilder sb = new StringBuilder();

        int TC = Integer.parseInt(bf.readLine());

        for(int t=0;t<TC;t++){

            int n = Integer.parseInt(bf.readLine());
            StringTokenizer st = new StringTokenizer(bf.readLine());
            result=0;
            // boards[i] = j => i->j
            Arrays.fill(boards,0);

            // 해당 노드가 이미 방문했는지 확인
            Arrays.fill(visited,false);

            // dfs 상에서 방문했는지 확인
            Arrays.fill(dfsVisited,false);

            for(int i=1;i<=n;i++){
                boards[i] = Integer.parseInt(st.nextToken());
            }

            for(int i=1;i<=n;i++){
                if(visited[i]){
                    continue;
                }

                dfs(i);
            }

            sb.append(n-result);
            sb.append("\n");

        }
        System.out.println(sb);
    }

    public static void dfs(int index){

        if(visited[index]){
            return;
        }

        // 해당 dfs에서 방문했던 경우 => 사이클 발생
        if(dfsVisited[index]){
            recNum=index;
            return;
        }

        dfsVisited[index]=true;

        dfs(boards[index]);

        if(recNum!=-1){
            result++;
            if(recNum==index){
                recNum=-1;
            }
        }
        visited[index]=true;

        dfsVisited[index]=false;


    }
}