[백준9466] 텀 프로젝트 / Java

링크 | https://www.acmicpc.net/problem/9466

문제 |

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

학생들이(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까지 번호가 부여된다.)

출력 |

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

예제 |

입력

2
7
3 1 3 7 3 4 6
8
1 2 3 4 5 6 7 8

출력

3
0

Solution |

1
7
3 1 3 7 3 4 6

• DFS 이용

• 모든 케이스의 DFS 실행하면 시간 초과 - 시간복잡도: O(n^2)

• 방문한 케이스와 사이클이 만들어진 케이스를 제외하여 시간복잡도 O(n)으로 구현.

• 단순히 방문한 경우->visted, 방문한 수에서 사이클을 발견한 경우->finished

• 싸이클을 만난 경우 싸이클에 속하는 숫자를 카운트.

• finshed 배열을 사용하지 않고 visited 배열만 사용하는 경우 순환 고리의 마지막 수의 next가 첫번째 수와 같은데 맨 처음 visited[]를 이미 true로 바꾸어주었기 때문에 return 되어버린다.
  ex) 4->7->6->4

cf) 시간복잡도를 O(n)으로 구현해야 시간초과가 나지않는다.

cf) 반례: 루틴 중간에 사이클이 생기는 경우도 확인해야한다.

2
6
2 3 4 5 6 2
5
3 3 1 2 1

참고한 코드

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

public class Main {
	static int V, cnt;
	static LinkedList<Integer> e[];
	static boolean[] visited;
	static boolean[] finished;
	
	public static void main(String[] args) throws IOException {
		int v;
		StringBuilder sb = new StringBuilder();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));			
			
		int K = Integer.parseInt(br.readLine());
		while (K--!=0) {
			V = Integer.parseInt(br.readLine()); // 정점

			visited = new boolean[V+1];
			finished = new boolean[V+1];
			e = new LinkedList[V+1];
			for (int i=1; i<=V; ++i) {
				e[i]=new LinkedList();
			}
			
			StringTokenizer vw = new StringTokenizer(br.readLine());
			for (int i=1; i<=V; i++) {	
				v = Integer.parseInt(vw.nextToken());
				e[i].add(v);
			}
			
			cnt=0;
			for(int i = 1; i<=V; i++) {	
				DFS(i);
			}
			
			sb.append(V-cnt).append('\n');
		}
		System.out.println(sb);
	}
	
	static void DFS(int idx) {
        if (visited[idx]) return; 
        
        visited[idx] = true;
        int next = e[idx].get(0);
        
        if (!visited[next]) {
        	DFS(next);
        }else {
        	// 사이클이 있는 경우
        	if (!finished[next]) {
        		cnt++;
        		while (next != idx) {
        			next = e[next].get(0);
        			cnt++;
        		}
        	}
        }
        finished[idx] = true;
	}
}