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

[Gold III] 텀 프로젝트 - 9466

문제 링크

성능 요약

메모리: 300236 KB, 시간: 1088 ms

분류

깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2023년 12월 23일 18:48:12

문제 설명

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

학생들이(s₁, s₂, ..., s_r)이라 할 때, r=1이고 s₁이 s₁을 선택하는 경우나, s₁이 s₂를 선택하고, s₂가 s₃를 선택하고,..., s_r-1이 s_r을 선택하고, s_r이 s₁을 선택하는 경우에만 한 팀이 될 수 있다.

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

1	2	3	4	5	6	7
3	1	3	7	3	4	6

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

출력

각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

 

풀이 방법

1. 학생수만큼 for문을 진행하면서 dfs를 한다.

2. 모든 노드는 무조건 다른 한개의 노드를 가르키기 때문에 싸이클에 들어가게 된다.

예시

1) 1 -> 3 -> 3 여기서 3-> 3이므로 싸이클이 끝난다. 

2) 2 -> 1 -> 3 -> 3 이므로 2에서 1로 간다면 굳이 싸이클로 들어갈 필요 없이 그냥 끝내면 된다.

3) 3 -> 3일 때 1을 더해주면 된다.

즉, 1번 학생을 탐색한다면 2,3번 학생은 탐색 할 필요가 없다.

3. 방문 경로를 저장하는 visit배열과 앞에서 진행한 적 있는 학생인가를 확인하는 finish배열이 있으면 된다.

4. dfs를 마치면 싸이클의 개수가 구해지므로 n에서 빼준다면 싸이클에 속하지 않는 학생의 수를 구할 수 있다. 

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

public class Main {
    static boolean[] visit, finish;
    static int[] students;
    static int n, answer;

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

        int TC = Integer.parseInt(br.readLine());
        for (int t = 0; t < TC; t++) {
            n = Integer.parseInt(br.readLine());

            // 방문여부를 저장하는 visit 배열
            visit = new boolean[n + 1];
            // 싸이클 여부를 저장하는 finish 배열
            finish = new boolean[n + 1];
            // 학생들이 선택한 학생을 저장하는 students 배열
            students = new int[n + 1];
            // 싸이클의 개수를 저장하는 answer 변수
            answer = 0;

            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= n; i++) {
                students[i] = Integer.parseInt(st.nextToken());
            }
            // 1 ~ n까지 dfs를 호출한다.
            for (int i = 1; i <= n; i++) {
                dfs(i);
            }
            // answer에는 싸이클의 개수가 세어져있기때문에 n - answer(싸이클에 축하지않는 학생의 수)
            sb.append(n - answer).append("\n");
        }
        System.out.println(sb);
    }

    private static void dfs(int cur) {
        // 이미 방문한 학생이라면 return;
        if (visit[cur]) {
            return;
        }

        // 현재 학생을 방문처리
        visit[cur] = true;
        // 현재 학생이 선택한 학생을 가져옴
        int select = students[cur];

        // 만약 다음 학생에게 방문을 안했다면 dfs호출
        if (!visit[select]) {
            dfs(select);
        }
        // 방문한 학생일 때
        else {
            // 방문했는데 finish가 false라면(즉, 싸이클이 마치지 않은 경우라면 시작 노드) cycle이 생성된 것.
            if (!finish[select]) {
                // 현재 학생을 더해준다.
                answer++;
                // 다음 학생부터 현재 학생까지 경로를 전부 더해준다.
                for (int s = select; s != cur; s = students[s]) {
                    answer++;
                }
            }
        }

        // 싸이클이 생성되든 안됐든 일을 마쳤으므로 true처리
        finish[cur] = true;
    }
}