[BOJ/GoldIII] 9466. 텀 프로젝트 - JAVA 자바

9466번: 텀 프로젝트

• 1484ms

# 접근방식
1부터 n까지 팀을 만들 수 있는지 판단한다

 

핵심은 1 → 2 → 3 → 4 → 5 → 2 가 되면 1은 팀이 될수 없고 2, 3, 4, 5 는 팀이 될 수 있다. 따라서 팀을 만들기 위해 함께 하고 싶은 학생들을 꼬리를 물고 탐색할 때, list에 추가하면서 탐색한다.

 

1. 다음 확인하는 학생이 list에 포함된다면 그 학생의 index부터는 팀을 만들 수 있다는 의미이다. 따라서 그 전 index 수만큼 팀을 못 만드는 학생이 추가된다.

 

만일 list의 시작점이라면 list에 있는 학생은 모두 팀을 만들 수 있으므로 0이 추가된다.

    if (checked[next] && list.contains(next)) {
                        result += list.indexOf(next);
                        break;
                    }

 

2. 다음 확인하는 학생이 혼자 하고 싶다면 list에 있는 모든 학생이 팀을 만들 수 없다.

     if (next == arr[next]) {
                         result += list.size();
                         checked[next] = true;
                         break;
                     }

 

3. 다음 확인하는 학생이 list에 없으면서 다른 팀에 포함된 상태라면 list의 모든 학생이 팀을 만들 수 없다.

                     if (checked[next]) {
                         result += list.size();
                         break;
                     }

 

위와 같은 조건을 나눠 팀을 만들 수 없는 학생을 카운트하고 팀에 포함되거나 포함되지 못하는 학생은 checked 배열을 통해 체크하여 탐색을 더욱 빠르게 할 수 있도록 구현하였다.

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

public class Main {
    static int index, n, m, result;
    static int[] arr;
    static boolean[] checked;
    static List<Integer> list = new ArrayList<Integer>();

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

        int T = Integer.parseInt(br.readLine());

        for (int t = 0; t < T; t++) {
            n = Integer.parseInt(br.readLine());
            arr = new int[n + 1];
            checked = new boolean[n + 1];

            result = 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 (checked[i])
                    continue;
                if (i == arr[i])
                    continue;

                index = i;
                checked[i] = true;
                list.add(i);

                while (true) {
                    int next = arr[index]; // index의 함께 하고 싶은 학생 => next

                    // next가 혼자하고 싶다면 list에 있던 사람들은 전부 팀에 속하지 않게 됨
                    if (next == arr[next]) {
                        result += list.size();
                        checked[next] = true;
                        break;
                    }

                    // next가 list에 포함된다면 list에서 next부터 list.size까지 같은 팀에 속함
                    // => next 이전 값들은 프로젝트에 속하지 않게 됨
                    if (checked[next] && list.contains(next)) {
                        result += list.indexOf(next);
                        break;
                    }

                    // next가 list에 포함되지 않으면서 체크했다면 list의 사람들은 팀에 속하지 않게됨
                    if (checked[next]) {
                        result += list.size();
                        break;
                    }

                    checked[next] = true;
                    list.add(next);
                    index = next;
                }
                list.clear();
            }
            sb.append(result).append('\n');
        }
        System.out.println(sb);
    }
}