백준 : 9466 (텀 프로젝트)

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

9466번: 텀 프로젝트

싸이클 구하기

싸이클에 포함되지 않는 노드들에 개수를 구하는 문제이다.
문제를 구하기 위해서 기존 DFS에서 vsisit boolean형에서 isCheck boolean형을 추가햇다.
DFS를 하면서 자기자신의 방문 여부를 check할때 visit으로 확인한다. 그렇게 DFS로 들어가다가 단방향 그래프라면 그다음 그래프가 visit이라면 사이클이 있다는 뜻이다.
이때는 현재노드부터 자기자신이 나올때까지 개수를 check하면 하나의 사이클이 이루는 node의 개수를 구할수가있다. 

여기서 visit하나의 boolean형만 잇다면 사이클에 포함되지 않는 node가 그다음은 node가 visit = true인것만으로는 이게 지금 내가 dfs를 타고와서 visit처리한건지 이전에 처리한것인지 알수가 없다.

따라서 isCheck 형을 만들어서 isCheck는 DFS가 재귀를 마치고 종료되는 시점에서 true를 만드는 용도로 쓴다.
따라서 다음노드가 visit =true이고 isCheck=false이라면 현재 내가 DFS를 통해서 만들어진 노드가 다시 순회하는 지점이라는 것을 알수가 있다.

isCheck = true 라면은 이전 DFSnode에서 탐사를 끝낸 노드라는것을 알수가 있다.

visit은 방문한적이 있는가 여부고
isCheck는 false일경우 그 node는 지금 DFS재귀안에 속한다는 뜻이다.

package com.ssay.algo;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class B9466 {
    static int T;
    static int N;
    static int Node[];
    static int Answer;
    static boolean visit[];
    static boolean isCheck[];
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        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());
            Node = new int[N+1];
            StringTokenizer st =new StringTokenizer(br.readLine());
            for(int j=1;j<=N;j++) {
                Node[j] = Integer.parseInt(st.nextToken());
            }
            
            visit = new boolean[N+1];
            isCheck = new boolean[N+1];
            
            Answer = N;
            
            for(int n=1;n<=N;n++) {
                if(visit[n])continue;
                DFS(n);
            }
            
            System.out.println(Answer);
            
        }
    }
 
    public static void DFS(int node) {
        visit[node] = true;
        
        if(!visit[Node[node]]) {
            DFS(Node[node]);
        }else if(visit[Node[node]] && !isCheck[Node[node]]) {
            //Answer 줄이기
            for(int n=Node[node];n!=node;n=Node[n]) {
                Answer--;
            }
            Answer--;
            
        }
        isCheck[node] = true;
        return;
    }
}