[그래프/문제] BOJ9466, 텀프로젝트 알고리즘, DFS Cycle

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

문제

문제는 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께 하고 싶은 학생들을 선택하는데

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

풀이

이 문제는 DFS를 활용하여 Cycle을 이루는지 확인하는 방법으로 문제를 풀 수 있다.

DFS를 하다가, 싸이클이 발생하는 조건을 찾을 수 있다.

정점 방문을 시작했는지 체크하는 visited 배열,

그 정점의 방문함수가 완전히 끝났는지를 체크하는 finished 배열이 필요햐다.

다음에 방문할 정점을 k라고 했을때, visited[k] = true, finished[k] = false인 경우이다.

예를들어 1->2->3->1 이 싸이클을 이룬다고 가정해보자.

1번 정점에서 DFS를 시작했을 때, 1번 정점이 2번 정점을 부르고 2번 정점이 3번 정점을 부른다.

3번 정점이 다시 1번정점을 부를려고 했을 때 visited[1] = true, finished[1] = false이다.

따라서 1->2->3->1 이 싸이클임을 알 수 있다.

또한, 1->2->3->4 의 그래프가 있다고 가정해보자.

2번 3번 정점의 방문이 끝났고, 1번 정점 DFS를 시작했을때,

1번정점이 다음에 부르려는 2번 정점의 경우 visited[2] = true, finished[2] = true 이므로

1번정점은 싸이클 안에 없음을 알 수 있다.

	visited[next] = false	visited[next] = true
finished[next] = false	아직 방문하지 않은 정점	현재 정점과 next가 하나의 싸이클에 속함
finished[next] = true	이런 경우는 없음	이미 모든 탐색이 끝난 정점. 현재 정점은 next가 싸이클 안에 있건 없건 절대 그 싸이클 안에 있을 수 없음

출처 : http://kks227.blog.me/220785731077

java구현

[출처] 깊이 우선 탐색(Depth-First Search) (수정 2016-08-23)|작성자 라이

//BOJ 9466
public class DFS_isCycle {
	static int n, S[], cnt; //학생들의 수, 선택된 학생들의 번호 , 싸이클에 속하는 정점의 개수 
	static boolean visited[], finished[];

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		for(int i=1; i<=T; i++){
			n = Integer.parseInt(br.readLine());
			st = new StringTokenizer(br.readLine());
			S = new int[n+1];
			for(int j = 1; j<=n; j++){
				S[j] = Integer.parseInt(st.nextToken());
			}			
			visited = new boolean[n+1];
			finished = new boolean[n+1];
			//각 컴포넌트에 대해 DFS시작
			cnt = 0;
			for(int k=1; k<=n; k++){
				if(!visited[k]) dfs(k);
			}
			System.out.println(n-cnt);	
		}
	}

	private static void dfs(int curr) {
		visited[curr] = true;
		int next = S[curr];	
		if(visited[next]){
			if(!finished[next]){
				for(int temp = next; temp!=curr; temp=S[temp])	cnt++;
				cnt++;//자기 자신 
			}
		}else	dfs(next);
		finished[curr] = true;
	}

}

http://kks227.blog.me 블로그를 참고하여 구현하였습니다.