백준 9466 텀 프로젝트

문제

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

학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.

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

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

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

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

---

코드

import java.io.*;
import java.util.*;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //테이스 케이스 갯수 입력 받기
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            //N 입력 받기
            int n = Integer.parseInt(br.readLine());

            //간선 배열 입력 받기
            int[] array = new int[n + 1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= n; i++)
                array[i] = Integer.parseInt(st.nextToken());

            //사이클을 형성하는 노드 수 count
            int count = 0;
            //방문 정보 배열 {방문 했는 지, 탐색을 완료 했는지}
            boolean[][] visited = new boolean[n + 1][2];

            //모든 노드에 대해서
            for (int i = 1; i <= n; i++) {
                //완료한 노드라면 continue
                if (visited[i][1])
                    continue;

                //DFS
                count+=dfs(visited, i, array);
            }

            bw.write(n - count + "\n");
        }

        bw.flush();
    }

    //탐색하다가 사이클을 발견하면 카운팅하고 리턴
    public static int dfs(boolean[][] visited, int node, int[] array){
        //완료된 노드라면 그대로 리턴
        if(visited[node][1])
            return 0;

        int next=array[node];

        //현재 노드를 재방문 했다면 카운트에 추가해주고 완료 표시
        if(visited[node][0]) {
            visited[node][1]=true;

            return 1+dfs(visited, next, array);
        }

        //현재 노드를 방문한 적이 없다면 방문 표시 후 다음 노드 이동
        visited[node][0]=true;
        int answer=dfs(visited, array[node], array);

        //이 노드는 다시 탐색할 일이 없으므로 완료 표시 후 리턴
        visited[node][1]=true;
        return answer;
    }
}

---

해결 과정

1. 사이클을 발견하면 해당 수를 카운트하면 되고, 사이클을 형성하지 않는 노드의 갯수를 세면 된다. 하지만 노드는 최대 10만개이므로 각각의 노드에서 전부 탐색해보면 시간 초과가 난다.
   한 노드에서 가리키는 노드는 무조건 1개 이므로,
   먼저 탐색 중에 사이클을 형성하는 노드들은 카운팅해준다.
   그리고 방문했던 모든 노드는 다시 탐색할 필요가 없으므로 완료 처리 해준다.

2. 😁