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

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

9466번: 텀 프로젝트

 

처음에 BFS로 접근하여 풀었다가 시간초과가 발생하여 DFS로 다시 풀게된 문제이다.

방문한 배열, 팀 구성 완료된 배열을 생성하여 포문을 돌면서 확인한다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
	static Map<Integer, Integer> map;
	static int donePeople = 0;
	static int people;
	static boolean visited[], done[];

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < n; i++) {
			map = new HashMap<>();
			people = Integer.parseInt(br.readLine());
			visited = new boolean[people + 1];
			done = new boolean[people + 1];
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 1; j < people + 1; j++) {
				map.put(j, Integer.parseInt(st.nextToken()));
			}

			donePeople = 0; //팀 구성된 인원

			for (int j = 1; j < people + 1; j++) {
				if (!done[j])
					check(j);
			}
			sb.append(people-donePeople+"\n");
			
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	static void check(int idx) {
		if(done[idx]) return;
		if(visited[idx]) {
			donePeople++;
			done[idx]=true;
		}
		visited[idx]=true;
		check(map.get(idx));
		visited[idx]=false;
		done[idx]=true;
	}

}