[백준_9466번] 텀 프로젝트

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

9466번: 텀 프로젝트

[문제]

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

학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다. 예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

 

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

 

 위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다. 주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

 

[입력 조건]

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

 

[코드]

import java.util.*;

public class BaekJoon_9466 {
	static int[] arr;
	static boolean[] visited, finished;
	static int n,count;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int testcase=sc.nextInt();
		
		while(testcase-->0) {
			n=sc.nextInt();
			visited=new boolean[n+1]; // 단순히 방문 여부를 체크하는 배열
			/*
			 * 해당 노드를 시작으로 하는 싸이클을 검출했는가 체크하는 배열 -> 중복을 방지하기 위해
			 * 예를들어 1->3->3과 2->1->3->3 두 개의 싸이클인 경우 앞의 1번 노드 탐색만으로
			 * 싸이클을 검출할 수 있다. 2번 노드를 끝까지 해도 같은 결과 검출 
			 */
			finished=new boolean[n+1]; 
			arr=new int[n+1];
			
			for(int i=1;i<=n;i++)
				arr[i]=sc.nextInt();
			
			count=0; // 팀을 이룬 학생의 수
			for(int i=1;i<=n;i++)
				dfs(i);
			
			System.out.println(n-count);
		}
	}
	
	static void dfs(int now) {
		if(visited[now]) // 탐색 시작 노드가 이미 방문했던 노드라면 종료
			return;
		
		visited[now]=true; 
		int next=arr[now];
		
		if(!visited[next])
			dfs(next);
		
		// 노드가 끝나려면 반드시 싸이클을 가져야함
		else {
			if(!finished[next]) { // 아직 싸이클을 탐색하지 않은 노드라면 
				// 싸이클에 포함되는 노드의 개수 count
				count++; 
				for(int i=next;i!=now;i=arr[i])
					count++;
			}
		}
		
		// 싸이클을 탐색했다면 더이상 해당 노드를 사용하지 않는다.
		finished[now]=true;
	}
}

 

[고찰]

 처음 문제를 접근했을 때는 싸이클을 찾아야 하는 문제임을 파악해 DFS 알고리즘으로 모든 싸이클을 찾는 방식으로 접근했더니 시간초과 결과를 얻었다. 어떻게 시간을 줄여야 하는지 떠오르지 않아 다른 사람의 코드를 참고했더니 해결 방법을 얻었다. 

 이번 문제는 모든 노드들은 반드시 다른 노드 한개를 가리킨다는 조건이 있다. 이 말은 DFS 탐색이 끝나기 위해서는 무조건 싸이클에 포함된다는 말과 같다. 예제에 나와있는 각 시작 노드를 보면 1->3->3, 2->1->3->3->, 3->3 모두 싸이클로 끝나는 것을 확인할 수 있다. 1번 노드를 탐색하면 2번, 3번 싸이클은 탐색할 필요가 없어진다. 따라서 단순히 방문 여부만 체크하는 배열과 해당 노드로 시작하는 싸이클을 탐색했는가 체크하는 배열 두 개를 사용해 중복된 경우는 탐색하지 않는 방식으로 시간초과를 없앨 수 있다. 

 해답을 봐도 이해하는데 시간이 좀 걸렸던 문제였다. 이런 문제의 해결방법도 스스로 떠올릴 수 있을 만큼 많은 연습을 해야겠다.