[BOJ 9466] 텀 프로젝트 (Java, DFS)

 

---

문제 링크

https://www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

---

해당 문제에 대한 아이디어가 떠오르지 않아, 기술 블로그를 찾아보았고
visit 배열 말고, finish 배열을 활용하여 그래프 노드를 구하는 기법을 알 수 있었다.

 

풀이 

- 각 case 별 사이클 발생하는 인원 수를 구한 후 전체 학생 수와의 차이 구함 

- N이 최대 10^5 이기때문에 O(N^2)으로 풀 경우 10^10 이므로 '시간 초과' 발생 가능

- finish 배열 활용하여 이미 탐색이 끝난 경로의 경우 재탐색하지 않도록 하여 시간 복잡도 O(N) 만에 풀이 가능

1 -> 3 -> 3  // 자기 자신 가르키는 경우
2 -> 1 -> 3 -> 3

4 -> 7 -> 6 -> 4  // 사이클 발생 ( = 팀)

5 -> 3 -> 3

---

제출 코드

import java.util.*;
import java.io.*;

public class Main {
    
   static StringBuilder sb = new StringBuilder();

    static int T, N, TEAM_COUNT;

    static int[] student;

    static boolean[] visit, finish;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        T = Integer.parseInt(st.nextToken());
        while(T > 0) {
            T -= 1;

            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            student = new int[N + 1];
            for(int i = 1; i <= N; i++) {
                student[i] = Integer.parseInt(st.nextToken());
            }

            visit = new boolean[N + 1];
            finish = new boolean[N + 1];
            TEAM_COUNT = 0;

            pro();
        }

        br.close();
    }

    static void dfs(int x) {
        visit[x] = true;

        int y = student[x];
        if(!visit[y]) {
            dfs(y);
        } else if(!finish[y]) {
            int cnt = 1;
            while(x != y) {
                y = student[y];
                cnt += 1;
            }

            TEAM_COUNT += cnt;
        }

        finish[x] = true;
    }

    static void pro() {
        for(int i = 1; i <= N; i++) {
            if(!visit[i]) dfs(i);
        }

        sb.append(N - TEAM_COUNT).append("\n");
    }

    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb);
    }
    
}