[JAVA] BJO 9466 : 텀 프로젝트

문제

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

 

 

 

풀이

사이클을 탐색하고, 해당 사이클에 포함되는 노드와 포함되지 않는 노드를 구분한다.

 

나의 경우 DFS 를 이용해 사이클을 탐색했고,

하나의 사이클을 발견할 때마다 해당 사이클 안에 포함된 노드들의 수를 count 해주었다.

 

이때 방문 표시를 bool 타입의 visited[] 가 아닌 3개의 상태를 저장할 수 있는 int형 visited 를 이용해주었다.

visited[] = 0 : 아직 방문 전
visited[] = 1 : 방문 중임
visited[] = 2 : 방문 끝(사이클 판정 완료)

 

 

코드

import java.util.*;

public class Main
{
    public static int ans = 0, n = 0;
    public static int[] visited = new int[100001];
    
	public static void main(String[] args) {
		
		int t;
		Scanner sc = new Scanner(System.in);
		t = sc.nextInt();
		for(int i=0; i<t; i++){
		    n = sc.nextInt();
		    int[] arr = new int[n+1];
		    for(int j=1; j<=n; j++){
		        arr[j] = sc.nextInt();
		    }
		    
		    // DFS 로 사이클만 확인 
		    for(int j=1; j<=n; j++){
		        if(visited[j] == 0){
		            DFS(arr, j); // 조건 따져서..
		        }
		    }
		    
		    System.out.println(n-ans);
		    
		    // 초기화
		    for(int j=1; j<=n; j++){
		        visited[j] = 0;
		    }
		    ans = 0;
		}
	}
	
	// cycle 탐색 
	public static void DFS(int[] arr, int cur){
        if(visited[cur] == 1){
            
            // 사이클 내의 노드 count
            int flag = arr[cur];
            int cnt = 0;
            while(flag != cur){
                flag = arr[flag];
                cnt++;
            } cnt++;
            ans += cnt;
            return;
        }
        
        // 이미 탐색 완료. return
        if(visited[cur] == 2){
            return;
        }
        
        // 방문 표시 
        visited[cur] = 1;
        
        // cur 이 선택한 학생 
        int next = arr[cur];
        DFS(arr, next);
    
        visited[cur] = 2;
    }
}

 

---

메모

사이클 탐색 시 항상 DFS 3 이용할 필요는 없다.
무방향 그래프의 경우 visited 2 충분.

사용하는 경우!
- 방향 그래프 + 사이클 탐지
- 경로 내에 동일 노드 등장 여부 체크 필요한 경ㅇ
- 각 노드가 한 곳만 가리키는 경우