[BOJ-9466] 텀 프로젝트(JAVA)

[BOJ-9466] 텀 프로젝트(JAVA)

728x90

백준 9466 텀 프로젝트

문제 설명

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

(단 한 명만 선택할 수 있고, 자기 자신도 선택할 수 있다.)

- 학생들이(S1, S2, S3, ... , Sr) 이라 할 떄 S1이 S1을 선택하는 경우나,

S1이 S2를, S2가 S3를, .., Sr-1이 S1을 선택하는 경우 한 팀이 될 수 있다.

- 예를 들어 아래와 같이 학생들이 선택을 했다고 가정해보자.

- 위 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있고, 1, 2, 5는 어느 팀에도 속하지 않게 된다.

- 주어진 선택의 결과를 보고, 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 구하라.

입력 값

- 첫째 줄에 테스트 케이스의 개수 T가 주어진다.

- 각 테스트 케이스의 첫 줄에는 학생의 수 n ( 2 <= n <= 100,000 )이 주어진다.

- 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다.

(모든 학생들은 1번부터 n번까지 번호가 부여된다.)

예제

문제 분석

- 이 문제는 살펴보면 사이클이 존재하는 학생들은 팀을 이루는 것이고,

그렇지 않은 학생들은 팀을 이루지 않게 되는 것이다.

- 즉, 해당 학생이 사이클에 속해 있는지 판단하는 문제이다.

- 간단하게 생각해보자면, 한 학생을 선택한 후 해당 학생을 시작으로 하여

다시 그 학생으로 돌아오는지 판단하면 된다.

- 다시 그 학생으로 돌아오는지 판단하는 방법은 DFS를 이용하면 된다.

DFS를 이용하여 다른 노드 탐색 시 시작 학생이 다시 나오는지 판단하면 된다.

- 이러한 방법으로 하게 되면, 학생수 N이고, 각 학생들은 하나의 학생을 가르키기 때문에

간선의 수도 N이 된다. 즉, 한 학생당 O(N)의 시간복잡도를 가지고 사이클에 속해 있는지 판단하게 된다.

- 결론적으로 간단하게 생각한 방법은 O($N^2$)의 시간복잡도를 가지게 된다.

다만, N의 최댓값은 10만이기 떄문에 각 테스트 케이스마다 100억의 시간이 소요된다.

즉, 이 방법은 불가능하다.

- 그렇다면 어떻게 해야 할까?

- 중복 체크하는 학생들을 제거해야 한다.

- 한 학생을 선택하여 그 학생과 연결된 모든 학생들을 탐색하면서 사이클이 있는지 판단한다.

- 사이클이 존재한다면, 그 사이클 안에 있는 학생들은 사이클에 포함된 학생들이라 표시한다.

- DFS를 돌면서 지났던 학생들은 다시 선택되어도 똑같은 결과를 가져오기 때문에 다시 방문하지 않도록 표시한다.

- 정리하자면,

1. 모든 학생들을 차례로 돌아가며 선택한다.

2. 한 학생을 시작으로 DFS를 돌면서 사이클이 있는지 판단한다.

(사이클 안에는 시작 학생이 포함되지 않을 수 있다.)

3. 사이클에 포함된 학생들은 팀을 이루었다는 표시를 한다.

4. 해당 DFS를 탐색하며 지났던 학생들을 따로 표시한다.

5. DFS종료 후 다시 1번으로 돌아가고, 3번에 의해서 표시된 학생들인 경우 스킵한다.

소스 코드

import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; // https://www.acmicpc.net/problem/9466 // 텀 프로젝트 public class Main { private static int boards[] = new int[100001]; private static boolean visited[] = new boolean[100001]; private static boolean dfsVisited[] = new boolean[100001]; private static int recNum=-1; private static int result=0; public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); int TC = Integer.parseInt(bf.readLine()); for(int t=0;t i->j Arrays.fill(boards,0); // 해당 노드가 이미 방문했는지 확인 Arrays.fill(visited,false); // dfs 상에서 방문했는지 확인 Arrays.fill(dfsVisited,false); for(int i=1;i<=n;i++){ boards[i] = Integer.parseInt(st.nextToken()); } for(int i=1;i<=n;i++){ if(visited[i]){ continue; } dfs(i); } sb.append(n-result); sb.append("

"); } System.out.println(sb); } public static void dfs(int index){ if(visited[index]){ return; } // 해당 dfs에서 방문했던 경우 => 사이클 발생 if(dfsVisited[index]){ recNum=index; return; } dfsVisited[index]=true; dfs(boards[index]); if(recNum!=-1){ result++; if(recNum==index){ recNum=-1; } } visited[index]=true; dfsVisited[index]=false; } }

from http://9327144.tistory.com/107 by ccl(A) rewrite - 2021-10-13 21:00:45