[백준 9466] 텀 프로젝트 / 자바 / dfs + cycle

#문제         

레벨: G3
알고리즘: dfs + cycle
풀이시간: 1시간
힌트 참조 유무:

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

---

#문제 풀이        

본 유형은 나에게는 신유형이다. 보통 dfs라면 cycle를 돌지 않고 한 번 간 곳은 visited[] 배열로 방문하지 않는다. 그러나 이 문제는 done[] 배열을 만들어 두 번 순회하여 dfs를 마친다. 한 번 순회로 dfs를 마칠 수 있지 않나? (그럴 수도 있을 것 같긴 하다..) 그러나. 가볍게 이해하기 위해서는 dfs를 두 번 도는 것이 좋다. 한 번 돌 때는 연결고리를 만드는 과정이고 두 번 순회할 때는 cycle인지 판별하여 팀원인지 가려내기 위함이다. 

 

---

#풀이 코드      

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static int T, N, res;
    private static int arr[];
    private static boolean visited[], done[];

    public static void dfs(int idx) {
        if(done[idx]) return; // 이전에 이미 검사했다는 뜻이므로 더 이상 들어갈 필요가 없다.
        if(visited[idx]) { // 방문을 했었다 == 사이클 구성원이다
            done[idx] = true; // 이제 다시 볼 일 없으므로 done 체크
            res++; // 사이클 구성원이므로 + 1
        }
        visited[idx] = true; // 방문 체크
        dfs(arr[idx]);
        done[idx] = true; // 사이클이 아닌 애들도 검사 끝났으니까 done 체크
        visited[idx] = false; // 방문 체크한 거 초기화
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        for(int t = 1; t <= T; t++) {
            N = Integer.parseInt(br.readLine()); res = 0;
            arr = new int[N + 1]; done = new boolean[N + 1]; visited = new boolean[N + 1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int n = 1; n <= N; n++) arr[n] = Integer.parseInt(st.nextToken());

            for(int i = 1; i <= N; i++) {
                if(done[i]) continue; // 이미 검사한 애들은 스킵한다.
                dfs(i);
            }
            System.out.println(N - res); // 사이클에 해당하지 않는 학생 수 출력
        }
    }
}