백준 9466 텀 프로젝트 java

문제 소개 www.acmicpc.net/problem/9466

내용

학생들은 텀 프로젝트를 수행해야 한다.

프로젝트 팀원 수에는 제한이 없다.

모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 

프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다.

(단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

 

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

 

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

입력

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

출력

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

해결 방법

아이디어

1. union-find에서 부모찾듯이 index -> nums[index] -> nums[nums[index]] -> ... 의 지나온 순서를 queue에 저장한다.
2. 그리고 지나갈 때마다 visited배열을 선언하여 지나갔다는 것을 표현한다.
3. 이후 ... -> nums[...[index]]이 이미 visited한 곳이라면 visited한 index를 저장한다.
4. 저장된 queue에서 index를 찾을때까지 queue에서 poll을 한다. 
5. poll한 횟수가 구하고자 하는 정답이다. 

이 아이디어는 모든 nums배열을 순회하면서 1번을 시도한다. 그러므로 모든 nums배열을 순횐하는데 필요한 시간은 n이 걸린다는 것은 자명하다. 그리고 반복문 안에 1~5번의 알고리즘이 돌아간다. 잘생각해보면 이미 1~5번 알고리즘을 통해서 visited 한 원소들은 다시 1~5번을 반복하지 않는다. 그러므로 모든 nums배열을 순회하는 것과 별개로 n만큼의 시간이 더 걸리기 때문에 총 시간은 2n 시간복잡도는 O(n)이라 표현할 수있다. 이는 n이 100,000이기 때문에 충분히 시간안에 동작할 수 있다.

실제 풀이 코드

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

        for (int i = 0; i < testCase; i++) {
            int n = Integer.parseInt(br.readLine());

            String[] split = br.readLine().split(" ");
            int[] nums = new int[n];
            for (int j = 0; j < n; j++) {
                nums[j] = Integer.parseInt(split[j]) - 1;
            }

            int answer = 0;

            boolean[] visited = new boolean[n];
            Queue<Integer> queue = new LinkedList<>();
            for (int j = 0; j < n; j++) {
                if (visited[j]) continue;
                visited[j] = true;

                int index = j;
                queue.add(index);
                while(!visited[nums[index]]){
                    index = nums[index];
                    visited[index] = true;
                    queue.add(index);
                }
                index = nums[index];

                while(!queue.isEmpty() && index != queue.peek()){
                    queue.poll();
                    answer++;
                }

                queue.clear();
            }

            sb.append(answer).append(System.lineSeparator());
        }
        System.out.println(sb.toString());
    }
}

결과

DFS문제라는 것을 풀고 나서 알게되었다. DFS를 활용하여 해결한다고 생각해보니 이해가 되었다. 하지만 n이 100,000이기때문에 재귀를 이용하여 해결하려했다면 stackoverflow가 발생했을지도 모르겠다.