백준 - 9466번 - 텀 프로젝트

9466번

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

public class Main{
	static StringBuilder sb = new StringBuilder();
	static int[] graph;
	static boolean[] check, finish;
	static int cnt;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(bf.readLine());

		for (int i = 0; i<n; i++) {
			int m = Integer.parseInt(bf.readLine());
			graph = new int[m+1];
			check = new boolean[m+1];
			finish = new boolean[m+1];
			cnt = 0;
			StringTokenizer st = new StringTokenizer(bf.readLine());
			for (int j = 1; j<m+1; j++) {
				graph[j] = Integer.parseInt(st.nextToken());
			}

			for (int k = 1; k<graph.length; k++) {
				if (!finish[k]) {
					dfs(k);
				}
			}
			sb.append(m - cnt).append('\n');
		}
		System.out.print(sb);
	}

	static void dfs(int k) {
		if (check[k]) {
			finish[k] = true;
			cnt++;
		}
		else {
			check[k] = true;
		}

		if (!finish[graph[k]]) {
			dfs(graph[k]);
		}

		check[k] = false;
		finish[k] = true;
	}
}

풀이

---

정점과 그 정점끼리 연결방향을 알려주고 사이클 그래프면 팀을 짤 수 있는데, 팀을 짜지 못한 학생의 수 를 출력하는 문제다.

지금까지 정점끼리 연결방향을 고려하지 않은 문제만 봐서 어떻게 구현할지 아주 생소했다. 또 사이클 그래프인지 또 그 사이클 그래프에 속한 정점들을 어떻게 추려낼지 머리가 아팠다.

하지만 정답은 학생의 수 이기 때문에 또 count 변수를 이용할것이다.

사이클 그래프는 dfs로 판별할수 있어 메서드를 만들고 정점끼리 연결방향을 나타내는 graph 배열, check 사이클 그래프인지 판별하는 배열, graph 배열을 탐색을 완료했는지 나타내는 배열 finish를 만들었다.

dfs메서드는 재귀형태를 띄고 1부터 graph배열의 인덱스를 각 배열의 값과 비교해서 만약 처음 설정한 수가 check된상태면 finish를 true 해주고 count를 세준다. check가 안된상태면 바로 check true해주고 graph[처음숫자]가 finish가 true됐는지 확인해서 안됐으면 재귀로 dfs(graph[처음숫자])해주고 돼있으면 check 풀고 마무리한다.

이게 재귀로 인해 처음으로 보내지면 check돼있는 숫자를 만날 수 있는데 그때 이 숫자가 사이클 그래프인지 알 수 있는것이다.

마지막에 배열의 크기 - 1 - count값(사이클그래프 내부 학생 수) 하면 된다.