[백준 / BOJ] 9466번 : 텀 프로젝트 (JAVA)

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

9466번: 텀 프로젝트

 

스스로를 지목한 사람 처리

가장 먼저 생각한 것은 "자기 자신을 지목하는 사람을 포함해서는 절대 사이클이 이뤄지지 않는다"였다. 스스로를 지목한다면 혼자 프로젝트를 하는 것으로 미리 표시하기로 했다. 그 사람을 포함해서는 팀을 만들 수 없기 때문이다. 

 

+) 일단 이 아이디어를 가장 먼저 생각해냈고, 이 부분을 포함한 코드로 정답 처리를 받았으나 나중에 확인해보니 아래 방문 체크를 한다면 스스로를 지목한 사람을 따로 처리할 필요가 없었다!

 

방문 체크

사이클이 있는지 확인하기 위해서는 방문 체크가 필요하다. 체크가 되어 있는 곳에 다시 방문하게 된다면 사이클이 존재하는 것이기 때문이다. 따라서 v라는 배열을 두었다.

 

하지만 단순히 방문한 적이 있는가 없는가로는 처리하기 어렵다. 사이클에 몇 명이 들어가 있는지도 확인해야 하기 때문이다. 따라서 visit이라는 변수를 두고 체크할 때마다 1씩 더해주었다. 단, 배열을 하나만 쓰고 싶어서 visit 외에, 이번 사이클 조사를 몇 번에서 시작했는지 알 수 있는 start라는 변수도 추가해주었다.

 

즉, 특정 사람을 시작으로 하기 전에 visit 변수를 start에 저장해둔다. 이를 통해 이미 조사 완료된 사람을 확인할 때에 이번에 조사한 사람인지, 아니면 다른 사람 기준으로 조사할 때 방문했던 곳인지 확인할 수 있다. 방문 체크된(v[i]가 0이 아닌 경우) 곳에 재방문하게 된다면, 일단 이번 조사 흐름 안에 있는지 확인하고(v[i]가 start와 같거나 큰지 확인) 있다면 visit - v[i]를 전체 count에 더해주는 것이다. count는 팀을 만든 사람의 명수이다.

 

팀을 못만든 사람의 수

총 팀을 만든 사람의 수를 count로 셌으니, 전체 인원 N에서 해당 값을 뺀 것이 정답이다.

 

전체 코드는 다음과 같다.

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		
		for (int t = 0; t < T; t++) {
			int N = Integer.parseInt(br.readLine()); // 전체 인원
			int[] team = new int[N];
			st = new StringTokenizer(br.readLine());
			int[] v = new int[N]; // 방문 체크할 배열
			
			int count = 0;
			for (int i = 0; i < N; i++) {
				team[i] = Integer.parseInt(st.nextToken()) - 1;
				if(team[i] == i) { // 자기 자신을 지목한 사람
					v[i] = 1;
					count++;
				}
			}
			
			Queue<Integer> que = new LinkedList<>();
			int visit = 2;
			for (int i = 0; i < N; i++) {
				if(v[i] == 0) { // 한 번도 방문한 적이 없다면
					que.offer(i);
					int start = visit; // 이번 조사를 시작한 번호
					v[i] = visit++; // 방문 체크
					while(!que.isEmpty()) {
						int cur = que.poll();
						if(v[team[cur]] != 0) { // 이미 방문했던 곳이라면
							if(v[team[cur]] >= start) { // 이번 조사 내에서 한 것인지 확인
								count += visit - v[team[cur]]; // 맞다면 해당 사람 ~ 현재까지의 수를 count에 더해줌
							}
							break;
						}
						que.offer(team[cur]); // 방문한 적 없다면 que에 넣어주고 visit으로 방문 체크
						v[team[cur]] = visit++;;
					}
					
				}
			}
			
			System.out.println(N - count);
		}
	}

}