1 분 소요

문제

문제 바로가기

입력

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

출력

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

접근방법

dfs를 이용하여 각 노드에서 출발하여 사이클을 이루는지를 확인하고 사이클을 이루지 않으면, 노드들의 개수를 카운트하여 해결할 수 있다. 문제는 간단했지만 푸는데 조금 시간이 걸렸다. 자세한 설명은 주석을 참고하면 된다.

풀이

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

public class Main {
    static int n, cnt;
    static int[] arr;
    static boolean[] check;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());

        while(T-- > 0) {
            n = Integer.parseInt(br.readLine());
            arr = new int[n+1]; 
            check = new boolean[n+1];
            cnt = 0;
            st = new StringTokenizer(br.readLine());
            for(int i = 1; i <= n; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }

            for(int i = 1; i <= n; i++) {
                if(!check[i]) {
                    List<Integer> temp = new ArrayList<>();
                    find(i, temp);
                }
            }

            sb.append(cnt + "\n");
        }

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }

    public static void find(int end, List<Integer> temp) {
        check[end] = true;  // 노드 방문 체크
        temp.add(end);      // 현재 경로에 노드 추가
        if(!check[arr[end]]) {
            find(arr[end], temp);  // 다음 노드가 방문하지 않은 경우 재귀호출 탐색
        }
        else {
            if(temp.contains(arr[end])) {   // 현재 경로에 다음 노드가 이미 포함되어 있을 경우
                cnt += temp.indexOf(arr[end]);  // 처음 시작된 노드부터 해당노드 이전까지의 노드의 개수를 더해줌
            }
            else {   // 현재 경로에 다음 노드가 포함되어 있지 않을 경우
                cnt += temp.size();  // 현재 경로의 모든 노드를 더해줌
            }
        }
    }
}

댓글남기기

참고