[백준] 9466번 텀 프로젝트

문제요약

텀 프로젝트를 조를 나누어 진행하려한다.
수업을 듣는 모든 학생들에게 함께 프로젝트를 진행하고 싶은 학생 한 명을 지목하여 제출하게 하였다.(본인을 제출하는 것도 가능하다)
조가 성립되기 위한 조건은 조의 구성원들이 사이클을 이루어야 한다는 것이다.
(Eg. a가 b를 지목하고, b가 c를 지목하고, c가 a를 지목한다면 a, b, c는 조를 이룰 수 있다)
위의 조건 하에서, 조를 이루지 못하는 학생의 수를 계산하는 프로그램을 작성한다.

코드

import java.io.*;
import java.util.*;
public class Main{
    static boolean[] visited;
    static boolean[] finished;
    static int cnt;
    static ArrayList<Integer> adj = new ArrayList<>();;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while (T != 0)
        {
            T--;
            int studentsNumber = Integer.parseInt(br.readLine());
            String[] info = br.readLine().split(" ");
            for (int i = 0 ; i < info.length; i++){
                adj.add(Integer.parseInt(info[i]) - 1);
            }
            visited = new boolean[studentsNumber];
            finished = new boolean[studentsNumber];
            cnt = 0;
            dfsAll();
            System.out.println(studentsNumber - cnt);
            adj.clear();
        }
    }
    public static void dfsAll(){
        for (int i = 0 ; i < visited.length ; i++) {
            if (!visited[i]) {
                dfs(i);
            }
        }
    }

    public static void dfs(int curr){
        visited[curr] = true;
        int adjStudent = adj.get(curr);

        if (visited[adjStudent]){
            if (!finished[adjStudent]){
                for (int t = adjStudent ; t != curr ; t = adj.get(t)){
                    cnt++;
                }
                cnt++;
            }
        }
        else
            dfs(adjStudent);
        finished[curr] = true;
    }
}	

dfs를 이용하여 문제를 해결하였다.
기본적인 dfs는 visited 배열 하나를 이용해서 방문하지 않은 노드들에 대한 탐색을 진행한다. 하지만 visited 배열 하나로는 사이클을 확인할 수 없다. 따라서 finished 배열을 하나 더 두어 사이클의 시작점을 확인하였다.

visited 배열은 탐색이 진행된 모든 노드들에 대해서 true 값을 가지지만 finished 배열은 현재 component에 속하는 노드들은 이미 방문되었더라도 false값을 가진다. 따라서 visited[next] = true, finished[next] = false라면 현재 노드에 인접한 next node가 이미 방문되었으나 이전 component가 아닌 현재 탐색 중인 component에 속하는 것이므로 cycle이 존재함을 알 수 있다.

문제에서 원하는 것은 조에 속하지 않는 인원이므로 cnt를 static으로 선언하여 cycle을 발견하면 해당 사이클에 속하는 학생(노드)의 수를 센 후 전체 학생 수에서 빼주었다.

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