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

 

 

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

- 단 한명만 선택 가능

- 자기 자신 선택 가능 (혼자서 팀)

 

1번~7번 학생들이 각자 팀을 이루고싶은 학생들을 선택한다고 가정하자.

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

어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 문제!!

 

 

싸이클을 형성하지 못하는 노드를 찾으면 되는데 시간초과가 발생한다..

이 때 '단 한명만 선택 가능' 이라는 조건을 이용하면 된다.

 

1->3->3

2->1->3->3

3->3

 

이 경우엔 1만 탐색한다면 2, 3은 할 필요가 없다!!!!

기존 dfs에서 쓰던 visited 배열로는 부족하고 하나 더 만들어줘야 한다.

visited가 방문 여부를 체크한다면,

새로 만들 배열은 방문한 노드가 싸이클을 만들었는가를 체크해준다.

 

1->3->3

visited[1] = visited[3] = true, visited[3]이 true이기 때문에 탐색 끝

+ 마지막 숫자는 싸이클을 형성할 수 밖에 없는데, 이 싸이클을 찾아 카운트 해준다.

++ 위 작업이 끝나면 1, 3에 대해 탐색이 끝났다고 새로 만든 배열에 표시한다.

 

위 작업을 반복하면 시간초과 없이 문제를 해결할 수 있다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ_9466 {
    static int n;
    static int[] arr;
    static int cnt = 0;
    static boolean[] visited;
    static boolean[] finished;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int T = Integer.parseInt(br.readLine());
 
        for(int i=0; i<T; ++i) {
            n = Integer.parseInt(br.readLine());
            arr = new int[n+1];
            visited = new boolean[n+1];
            finished = new boolean[n+1];
            cnt = 0;
 
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=n; ++j){
                arr[j] = Integer.parseInt(st.nextToken());
            }
 
            for(int j=1; j<=n; ++j){
                dfs(j);
            }
 
            System.out.println(n - cnt);
        }
    }
 
    static void dfs(int now) {
        if(visited[now]) return;
 
        visited[now] = true;
        int next = arr[now];
 
        if (!visited[next])
            dfs(next);
        else {
            if (!finished[next]) {
                ++cnt;
                for (int i=next; i!=now; i=arr[i])
                    ++cnt;
            }
        }
 
        finished[now] = true;
    }
}