Baekjoon 9466 텀 프로젝트 JAVA

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.io.*;
import java.util.*;

public class Main {
	static int [] students;
	static int n;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T=Integer.parseInt(br.readLine());
		for(int t=0;t<T;t++) {
			n=Integer.parseInt(br.readLine());
			students = new int [n+1];
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			for(int i=1;i<=n;i++)
				students[i]=Integer.parseInt(st.nextToken());

			System.out.println(find());
		}
	}

	static int find(){
        int[] links = new int[n+1];
        int ans = n;

        for (int i = 1; i <= n; i++) {
            int current = i;
            while (links[current] == 0){	// 탐색하지 않았다면 방문 가능한 상태
                links[current] = i;	// 현재 깊이에서 탐색했다는 것을 i값을 주어서 체크
                current = students[current];	// 연쇄적으로 값을 이어나감
            }	// -> 사이클이 생기기 전까지 계속해서 확인

            if (links[current] == i){	// 현재 깊이에서 탐색한 단계라면 체크
                int start = current;	// 위에 while문에서 반복을 이용하여 사이클을 찾았기에, 마지막 위치는 current임
                ans--;	// a->a로 가는 경우 하단의 while을 반복을 안하기에, ans--
                while ((current = students[current]) != start)	// 마지막으로 방문한 위치에서 전체를 찾아나가면서 한번의 사이클이 될때까지 탐색하여 조가 형성된 팀원수를 출력
                    ans--;
            }
        }
        return ans;
    }
	
//	static int [] students, chk;
//	public static void main(String[] args) throws Exception{
//		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//		int T=Integer.parseInt(br.readLine());
//		for(int t=0;t<T;t++) {
//			int n=Integer.parseInt(br.readLine()), ans=0;
//			students = new int [n+1];
//			chk = new int [n+1];
//			StringTokenizer st = new StringTokenizer(br.readLine());
//			
//			for(int i=1;i<=n;i++) {
//				students[i]=Integer.parseInt(st.nextToken());
//				if(students[i]==i)	// 혼자서만 하는 사람은 바로 체크해준다.
//					chk[i]=1;
//			}
//			// chk값 정보
//			// -1 : 팀구성 불가능, 0 : 탐색 X 혹은 탐색했찌만 다른 팀구성이 가능한경우 초기화, 1 : 팀구성 완료 
//			for(int i=1;i<=n;i++) {	// 처음 사람부터 탐색을 하면서 팀 구성 가능한 방법을 찾음
//				if(chk[i]==0)
//					if(dfs(i, i, students[i], new HashSet<Integer>())==0)	// 팀구성을 했을때 return이 0이면 만들어진 경로안에서 시작점이 다르면 구성할 수 있는 팀이 있음
//						chk[i]=-1;	// 시작하는 점만 구성못하는 것으로 체크
//			}
//			
//			for(int i=1;i<=n;i++)
//				if(chk[i]==-1)
//					ans++;
//			bw.write(ans+"\n");
//		}
//		bw.close();
//	}
//	
//	static int dfs(int start,int cur, int next, HashSet<Integer> hs) {
//		if(start==next)	// 시작점과 다음으로 보는 점이 동일한 경우, 하나의 사이클이 형성된 것
//			return chk[cur]=1;	// 현재점을 팀 구성 가능으로 적고, 모든 경로에 적용
//		if(chk[cur]==0) {	// 방문 하지 않았을 경우
//			chk[cur]=2;	// 방문 체크
//			hs.add(cur);	// 구성되는 사이클의 변수값들을 저장
//			chk[cur]=dfs(start, next, students[next], hs);
//			return chk[cur];
//		}
//		else {
//			if(hs.contains(next))	// 구성된 경로에 갈 수 있는 경로가 있다면 시작점을 바꾼다면 다른 학생으로 부터 시작하는 팀구성 가능
//				return 0;
//			else
//				return -1;	// 구성할 수 있는 팀이 없기에 전체를 구성 불가능으로 체크
//		}
//	}
}