[Java] 백준 9466번 - 텀 프로젝트

[문제]

 

[풀이]

팀을 결성하기 위해선, 결국 루프를 돌아야 한다는 조건을 떠올리면 쉽게 풀 수 있는 문제였습니다.

예를 들어 d -> a -> b -> c - > a 루프가 돈다면, a를 만났을때 이전 [d,a,b,c]중에 a가 존재하기 때문에 이는 루프가 됩니다. 즉, a의 index부터 팀을 결성할 수 있습니다.

• student[]에 index에서 이동할 숫자를 저장
• 만약 index -> index 라면, 혼자 팀을 이루기 때문에 total++ 을 통해 1명의 팀을 결성하고, visit[index] = true를 통해 방문 처리
• findTeam(student, N)을 통해 student배열을 돌며, 방문하지 않은 학생들만 while문을 통해 팀 결성을 시도합니다. 만약, 지나온 학생들의 ArrayList arr에 현재 방문한 학생이 있다면 루프를 만났으니 팀을 결성하고 탈출하여 total을 갱신합니다.
• 마지막에 N - total을 통해 팀을 결성하지 못한 학생수를 출력합니다.

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static int total = 0;
    public static boolean[] visit;
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int t=0;t<T;t++) {
            int N = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] student = new int[N+1];
            visit = new boolean[N+1];
            for(int i=1;i<=N;i++) {
                student[i] = Integer.parseInt(st.nextToken());
                if(i == student[i]) {
                    visit[i] = true;
                    total++;
                }
            }
            findTeam(student, N);
            sb.append(N-total + "\n");
            total = 0;
        }
        System.out.println(sb.toString());
    }
    public static void findTeam(int[] student, int N) {
        for(int i=1;i<=N;i++) {
            if(visit[i]) {
                continue;
            }
            int index = i;
            ArrayList<Integer> arr = new ArrayList<>();
            while(!visit[index]) {
                visit[index] = true;
                arr.add(index);
                index = student[index];
                if(visit[index] && arr.contains(index)) {
                    total = total + arr.size() - arr.indexOf(index);
                }
            }
//            System.out.println(arr);
        }
    }
}