[BOJ] 백준 [9466] 텀 프로젝트 JAVA

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

9466번: 텀 프로젝트

문제

풀이

총 2가지 풀이 방법으로 접근할 수 있다.
1. SCC 로 강한 결합요소를 전부 찾아서 (요소가2이상 혹은 셀프 사이클인 부분) 전체N에서 빼는방법
2. dfs 사이클 탐지 방법

 

1. SCC 풀이 방법

SCC는 scc집합들을 담은 ArrayList라고 할때 , SCC를 반복문으로 돌려서
scc의 크기가 2이상이거나 , 1이지만 셀프참조를 할 경우에 전체 N에서 그 만큼 갯수를빼주면
팀에 속하지 않은 인원이 나온다.

 

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
public class Main {
    static Stack<Integer> stack;
    static ArrayList<ArrayList<Integer>> SCC;
    static int N,index;
    static int[] discover;
    static boolean[] finish;
    static ArrayList<Integer>[] list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        while(tc-->0){
            N = Integer.parseInt(br.readLine());
            int[] input = new int[N+1];
            String[] e = br.readLine().split(" ");
            for(int i=1;i<=N;i++) input[i]=Integer.parseInt(e[i-1]);
 
            init();
            for(int i=1;i<=N;i++) list[i].add(input[i]); // 그래프 연결
            for(int i=1;i<=N;i++) if(discover[i]==0) dfs(i);
 
            int notTeam=N;
            for (ArrayList<Integer> scc : SCC) {
 
                if(scc.size()>=2 || scc.size()==1 && input[scc.get(0)]==scc.get(0)){
                    notTeam = notTeam-scc.size();
                }
            }
            System.out.println(notTeam);
        }
 
    }
 
    private static void init() {
        index=0;
        stack = new Stack<>();
        discover = new int[N+1];
        list = new ArrayList[N+1];
        finish = new boolean[N+1];
        SCC = new ArrayList<>();
        for(int i=1;i<=N;i++) list[i] = new ArrayList<>();
    }
 
    private static int dfs(int cur) {
        discover[cur] = ++index;
        stack.push(cur);
 
        int parent = discover[cur];
        for (Integer next : list[cur]) {
            if(discover[next]==0) parent = Math.min(dfs(next),parent);
            else if(!finish[next]) parent = Math.min(parent,discover[next]);
        }
 
        if(parent==discover[cur]){
            ArrayList<Integer> scc = new ArrayList<>();
            while(true){
                Integer pop = stack.pop();
                scc.add(pop);
                finish[pop] = true;
                if(pop==cur) break;
            }
            SCC.add(scc);
        }
        return parent;
    }
}
 
 

 

2. 싸이클 탐지방법

1->2->3->1 로 돌아오는 경우를 예시로 들어보자.
그럼 마지막 3이 호출한 dfs의 next는 1인데 , 1이 호출한 dfs가 아직 끝나지 않았으니
finish[1] = false가 되므로 사이클이란것을 알 수 있다.
3이 호출한 dfs의 next(1) 부터 cur로 돌아올 때 까지 cnt를 늘려주면서
사이클에 속한 노드가 몇개인지 카운트하면 끝
이런식으로 모든 노드를 방문하여 센 cnt 값을 총 노드의 갯수 N에서 빼준 N-cnt 가 정답이다.

 

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
public class Main {
    static int N,cnt;
    static boolean[] visit;
    static boolean[] finish;
    static ArrayList<Integer>[] list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        while(tc-->0){
            N = Integer.parseInt(br.readLine());
            int[] input = new int[N+1];
            String[] e = br.readLine().split(" ");
            for(int i=1;i<=N;i++) input[i]=Integer.parseInt(e[i-1]);
 
            init();
            for(int i=1;i<=N;i++) list[i].add(input[i]); // 그래프 연결
            for(int i=1;i<=N;i++) if(!visit[i]) dfs(i);
 
            System.out.println(N-cnt);
        }
 
    }
 
    private static void init() {
        cnt=0;
        list = new ArrayList[N+1];
        finish = new boolean[N+1];
        visit = new boolean[N+1];
        for(int i=1;i<=N;i++) list[i] = new ArrayList<>();
    }
 
    private static void dfs(int cur) {
 
        visit[cur] = true;
 
        for (Integer next : list[cur]) {
            if(!visit[next]) dfs(next);
            else if(!finish[next]){
                cnt++;
                for(int i=next;i!=cur;i=list[i].get(0)) cnt++;
            }
        }
        finish[cur]=true;
    }
}
 
 

 

시간차이는 SCC > dfs 사이클탐지 순으로 후자가 덜 걸린다.