백준 9466 - 텀 프로젝트

Java

9466 번 - 텀 프로젝트

문제

• 모든 학생은 프로젝트를 함께하고 싶어하는 학생을 한 명씩 선택한다. (자신도 가능)
• 서로 가리키는 학생 끼리 사이클이 형성되면 한 팀이 된다.
• 사이클을 형성하지 못한 학생들은 어떤 팀에도 속하지 않는다. 이 수를 구하자

접근 방법

깊이 우선 탐색(DFS)를 사용하여 현재 학생이 가리키는 학생들을 지속하여 탐색한다.
만약 학생을 타고 들어가다 사이클이 형성되면, 사이클을 형성된 학생들과 사이클에서 벗어난 학생들의 상태를 지정해 준다.

각 학생들의 상태를 총 4개로 나타내었다.

0 : 아직 방문하지 않았을 때
1 : 사이클이 형성 된 학생
2 : 사이클을 형성 하지 못한 학생
3 : 현재 탐색 중인 학생 

1. 방문 하지 않은 학생들을 하나씩 탐색한다.
2. 현재 학생이 가리키고 있는 다른 학생을 차례로 탐색하며, 방문 여부를 3으로 현재 탐색 중이라고 표시한다.
3. 계속 타고 들어가다, 현재 학생이 가리키는 학생의 상태가 현재 탐색 중인 상태이면 사이클이 형성 된 것이다.
4. 다시 현재 DFS를 함수를 호출한 학생으로 되 돌아 가면서, 사이클을 형성한 학생들의 상태를 1로 변경시킨다.
5. 처음 사이클을 형성한 학생을 가리키던 이전 학생들은 모두 사이클을 형성할 수 없으므로 상태를 2로 변경시킨다.

이후 아직 탐색하지 않은 학생들이 다른 학생을 가리킬 때, 그 학생의 상태가 이미 결정되어 있으면 사이클을 형성할 수 없으므로 상태를 2로 변경시칸다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, result;
	static int[] stud;
	static int[] state;	// 0은 방문하지 않은 상태, 1은 성공, 2는 실패, 3은 현재 탐색 중
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	int tcN = stoi(br.readLine());
    	for(int idx = 0; idx < tcN; idx++) {
    		n = stoi(br.readLine());
    		result = 0;
    		stud = new int[n+1];
    		state = new int[n+1];
    		
    		stk = new StringTokenizer(br.readLine());
    		for(int i = 1; i <= n; i++) {
    			stud[i] = stoi(stk.nextToken());
    		}
    		
    		for(int i = 1; i <= n; i++) {
    			if(state[i] == 0) {		// 아직 방문하지 않았으면
    				DFS(i);
    			}
    		}
    		
    		for(int i = 1; i <= n; i++) {
    			if(state[i] == 2)	// 실패한 경우를 센다
    				result++;
    		}
    		
    		System.out.println(result);
    	}
    	  	
    	br.close();
	}
	static int startN;
  	
	static int DFS(int curN) {
		if(curN == stud[curN]) {	// 자기 자신을 선택한 경우
			state[curN] = 1;		// 성공
			return 2;	// 현재 N을 가리켰던 모든 체인은 다 실패함
		}
		
		if(state[curN] == 3) {	// 사이클이 형성된 경우
			startN = curN;		// 사이클의 시작점을 저장한다
			return 1;
		}
		else if(state[curN] != 0) {		// 이미 한번 방문한 경우
			return 2;
		}
		
		state[curN] = 3;		// 현재 노드는 탐색 중
		
		int rst = DFS(stud[curN]);	
		
		if(rst == 1) {		// 사이클이 형성 되었다는 경우
			state[curN] = 1;
			
			if(curN == startN)	// 현재 노드가 사이클의 시작점이면, 현재 노드를 가리키던 다른 노드들은 실패한다.
				return 2;
			
			return 1;
		}
		else {		// 실패한 경우
			state[curN] = 2;
			return 2;
		}
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

오래 걸렸다.
처음에 Disjoint set으로 접근하려다, 잘 안되어 현재 문제의 분류를 보고 난 이후 풀이법이 생각나서 해결하였다.

개선할 점

없습니다.