[BaekJoon] 9466 텀 프로젝트 (Java)

1.  문제 링크

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

2.  문제

요약

• 학생들은 텀 프로젝트를 수행해야 하는데, 프로젝트 팀원 수에는 제한이 없고 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있습니다.
• 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께 하고 싶은 학생 한 명을 선택해야 하는데, 혼자 하고 싶은 학생들은 자기 자신을 선택하는 것도 가능합니다.
• 학생들이 ($s_1, s_2, ..., s_r$)이라 할 때, r = 1이고 $s_1$이 $s_1$을 선택하는 경우나, $s_1$이 $s_2$를 선택하고, $s_2$가 $s_3$를 선택하고, ... , $s_{r - 1}$이 $s_r$을 선택하고, $s_r$이 $s_1$을 선택하는 경우에만 한 팀이 될 수 있습니다.
• 주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 문제입니다.
• 입력: 첫 번째 줄에 테스트 케이스의 개수 T가 주어지고 각 테스트 케이스의 첫 번째 줄에는 2보다 크거나 같고 100,000보다 작거나 같은 정수인 학생의 수 n이 주어지고 두 번째 줄에는 선택도니 학생들의 번호가 주어집니다.
  • 모든 학생들은 1부터 n까지의 번호가 부여됩니다.
• 출력: 각 테스트 케이스마다 각 줄에 프로젝트 팀에 속하지 못한 학생들의 수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static Reader scanner = new Reader();
	static int n, count;
	static int[] selected;
	static boolean[] visited, finished;
	static void input() {
		n = scanner.nextInt();
		selected = new int[n + 1];
		visited = new boolean[n + 1];
		finished = new boolean[n + 1];
		count = 0;
		for(int idx = 1; idx <= n; idx++) selected[idx] = scanner.nextInt();
	}
	
	static void solution() {
		for(int student = 1; student <= n; student++) dfs(student);
		sb.append(n - count).append('\n');
	}
	
	static void dfs(int student) {
		if(visited[student]) return;
		visited[student] = true;
		int next = selected[student];
		if(!visited[next]) dfs(next);
		else {
			if(!finished[next]) {
				count++;
				for(int idx = next; idx != student; idx = selected[idx]) count++;
			}
		}
		finished[student] = true;
	}
	
	public static void main(String[] args) {
		int T = scanner.nextInt();
		while(T-- > 0) {
			input();
			solution();
		}
		System.out.println(sb);
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}