[백준] 9466번 : 텀 프로젝트 - 자바(JAVA)

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

9466번: 텀 프로젝트

 

문제 해석

프로젝트 팀원 수에는 제한이 없습니다.

모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 합니다.

혼자 하고 싶어 한다면 자기 자신을 선택하는 것도 가능합니다.

 

예시로 한반에 7명의 학생들이 존재하고 학생들을 1번부터 7번으로 표현할 때 선택의 결과는 다음과 같습니다.

 

1

2

3

4

5

6

7

 

3

1

3

7

3

4

6

 

위의 결과를 통해 (3)과 (4 7 6)은 팀을 이룰 수 있지만 1,2,5는 팀을 이룰 수 없습니다.

 

결국에는 싸이클이 이루어져야 팀을 이룰 수 있습니다.

 

어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하세요

 

문제 풀이 전 설계

cycle이 이루어지는지 탐색합니다.

만약 cycle이 이루어진다면 cnt를 더하고 최종 학생수에서 - cnt를 하는 식으로 정답을 유추합니다.

 

코드

import java.io.*;
import java.util.*;

public class Main_9466_텀프로젝트 {

    static int n, cnt;
    static int[] studentChoiceInfo;
    static boolean[] check, isSearchEnd;

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

        for (int test = 0; test < t; test++) {
            n = Integer.parseInt(br.readLine());
            studentChoiceInfo = new int[n + 1];
            check = new boolean[n + 1];
            isSearchEnd = new boolean[n + 1];

            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= n; i++) {
                int selectedStudent = Integer.parseInt(st.nextToken());
                studentChoiceInfo[i] = selectedStudent;
            }

            cnt = 0;
            for (int i = 1; i <= n; i++) {
                dfs(i);
            }
            System.out.println(n - cnt);
        }

    }

   
    static void dfs(int curStudent) {
        check[curStudent] = true;
        int nextStudnet = studentChoiceInfo[curStudent];
        //방문되지 않았으면 체크
        if (!check[nextStudnet]) {
            dfs(nextStudnet);
        }
        //이미 방문되었으며 싸이클탐색이 안되었다면
        if (!isSearchEnd[nextStudnet]) {
            cnt++;
            //싸이클이 나올때까지
            while (nextStudnet != curStudent) {
                cnt++;
                nextStudnet = studentChoiceInfo[nextStudnet];
            }
        }
        //이미 방문되고 싸이클탐색이 완료되었다면
        isSearchEnd[curStudent] = true;
    }
}