[백준] G3 9466번 텀 프로젝트 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

[문제] 

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

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

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

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

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

[입력]

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

[출력]

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

 

---

[풀이]

1. 값들을 입력받아 담아준다.

2. dfs 탐색을 한다.

3. 이미 탐색한 것이라면 리턴한다.

4. 현재 위치를 방문 처리한다.

5. 다음 위치는 배열에 담긴 현재 값이므로 해당 값을 담아준다.

6. 이미 탐색한 것이 아니라면 dfs 탐색을 해준다.

7. 이미 탐색을 했던 것이라면 사이클이 형성되었는지 판단하고 사이클 형성이 되어있지 않다면 모든 사이클을 탐색해준다.

8. 사이클 탐색을 완료 처리해준다.

9. 결과를 출력한다.

[접근]

1. 일반적인 dfs 탐색을 하면 되겠다고 생각하였다.

2. 하지만 이미 탐색을 하면서 사이클이 형성되어있는 것이라면 추가적인 탐색이 필요 없기에 이를 처리해주었다.

[코드]

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

public class Main {
	static int n;
    static int[] arr;
    static int count = 0;
    static boolean[] visited;
    static boolean[] finished;
    
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int tc = Integer.parseInt(br.readLine());
 
        for (int t = 0; t < tc; t++) {
            n = Integer.parseInt(br.readLine());
            arr = new int[n + 1];
            visited = new boolean[n + 1];
            finished = new boolean[n + 1];
            count = 0;
 
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            // 배열에 값을 넣기
            for(int i = 1; i < n + 1; i++) 
                arr[i] = Integer.parseInt(st.nextToken());
 
            // dfs 탐색
            for(int i = 1; i < n + 1; i++)
                dfs(i);
 
            System.out.println(n - count);
        }
    }
 
    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]) {
                count++; // 횟수 증가
                // 다음부터 지금이 아닐때까지 배열의 값으로 이동하면서
                for (int i = next; i != now; i = arr[i])
                    count++; // 카운트 증가
            }
        }
        
        finished[now] = true;
    }
}