b9466. 텀 프로젝트

 

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

 

 

 

 방향 그래프에서 사이클(순환 구조)에 포함되지 않은 노드의 수를 계산하는 문제다.
입력으로 주어진 각 테스트 케이스에 대해 그래프를 구성하고,
DFS(깊이 우선 탐색)를 활용하여 사이클을 탐지하며 노드를 처리하는 방식으로 풀이하였다.

먼저 테스트 케이스의 수 T를 입력받고,
 각 테스트 케이스에 대해 노드의 개수 n과 그래프의 연결 정보를 입력받는다.
그래프는 배열 arr로 표현되며, 각 노드가 가리키는 다음 노드를 저장한다.
배열 isVisited는 노드의 방문 여부를,
isChecked는 해당 노드가 이미 처리가 완료되었는지를 나타낸다.

DFS를 통해 각 노드를 탐색하며, 방문한 노드를 기록하고,
다음 노드로 이동한다.
만약 방문하지 않은 노드를 발견하면 재귀적으로 탐색을 이어가고,
이미 방문한 노드에 도달한 경우 사이클 여부를 확인한다.

사이클을 발견하면,
사이클에 포함된 모든 노드를 순회하며 사이클의 크기를 증가시킨다.
사이클에 포함되지 않은 노드의 수는 전체 노드 개수 n에서
사이클에 포함된 노드의 수를 뺀 값으로 계산된다.

n - count 값이 정답이 된다.

 

 

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

public class b9466 {

    static int n,count = 0;
    static int[] arr;
    static boolean[] isVisited, isChecked;

    static int stoi(String s){ return Integer.parseInt(s); }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = stoi(br.readLine());

        for (int t = 0 ; t < T ; t++){
            n = stoi(br.readLine());
            arr = new int[n+1];
            isVisited = new boolean[n+1];
            isChecked = new boolean[n+1];
            count = 0;

            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= n ; i++)
                arr[i] = stoi(st.nextToken());

            for (int i = 1; i <= n ; i++){
                dfs(i);
            }
            System.out.println(n - count);
        }
    }
    public static void dfs(int now){
        if(isVisited[now]) return;

        isVisited[now] = true;
        int next = arr[now];

        if (!isVisited[next])
            dfs(next);
        else {
            if (!isChecked[next]){
                count ++;
                for (int i = next ; i != now ; i = arr[i])
                    count++;
            }
        }
        isChecked[now] = true;
    }
}