[백준]#9466 텀 프로젝트

문제

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

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

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

예제 출력 1

3
0

풀이

이 문제는 DFS 알고리즘을 이용해서 풀 수 있는 문제이다. 시작한 번호와 방문했는 여부를 저장하고 이미 방문한 번호를 방문했을 때 시작 번호가 사이클이 생겼다고 확정할 수 있다.

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

public class Main {
    static int[] map;
    static int[] first;
    static int[] visited;

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

        for(int i=0; i<T; i++) {
            int N = Integer.parseInt(br.readLine());
            map = new int[N+1];
            visited = new int[N+1];
            first = new int[N+1];

            String[] input = br.readLine().split(" ");

            for(int j=1; j<=N; j++)
                map[j] = Integer.parseInt(input[j-1]);

            int cnt=0;
            for (int j=1; j<=N; j++) {
                if(visited[j]==0)
                    cnt+=dfs(j, j, 1);
            }
            System.out.println(N-cnt);
        }
    }

    static int dfs(int start, int current,  int cnt) {
        if(visited[current]>0) {
            if(first[current] != start)
                return 0;
            else
                return cnt-visited[current];
        }

        else {
            first[current]=start;
            visited[current]=cnt;
            return dfs(start, map[current],cnt+1);
        }
    }
}