[BOJ] 9466 - 텀 프로젝트 JAVA

www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

문제

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

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

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

1234567

3

1

3

7

3

4

6

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

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

입력

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

출력

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

예제 입력 1

2

7

3 1 3 7 3 4 6

8

1 2 3 4 5 6 7 8

예제 출력 1

3

0

 

 

 

 

 

 

풀이 .

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

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static int[] map = null;
    static int[] check = null;
    static boolean isCycle;
    static int cycleStartNode;
    static ArrayList<Integer> cycleNode = null;

    public static void dfs(int node, int dfsCnt) {
        int next = map[node];
        if(check[next] == 0) {
            check[next] = dfsCnt;
            dfs(next, dfsCnt);
        }else if(check[next] == dfsCnt) {
            isCycle = true;  // cycleStartNode 나올 때까지 true값 유지
            cycleStartNode = next;
        }

        if(isCycle) {
            cycleNode.add(node);
        }
        if(node == cycleStartNode) {  // 사이클에 포함되는 노드 수집 완료
            isCycle = false;
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));

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

            int dfsCnt = 1;  // 이미 센 사이클을 또 세지 않기 위함
            cycleNode = new ArrayList<>();
            for(int i = 1; i <= n; i++) {
                if(check[i] == 0) {
                    check[i] = dfsCnt;
                    dfs(i, dfsCnt);
                    dfsCnt += 1;
                }
            }

            System.out.println(n - cycleNode.size());  // 사이클에 포함되지 못한 노드 개수
            cycleStartNode = 0;  // 초기화
        }
    }
}

 

N 제한이 커서 까다로운 문제.

 

주의할 점,

1. DFS를 돌다가 사이클이 등장한다고 해도 해당 DFS에서 탐색한 모든 노드가 사이클에 포함되지는 않는다. 사이클에 포함되는 노드만 체크할 수 있어야 한다 . (예제의 경우에서 1 -> 3 -> 3 으로 사이클 완성됐지만 1은 포함되지 않음)

2. 사이클을 찾았다고 해도 이전 DFS에서 이미 찾았던 사이클일 수 있다. (예제의 경우에서 5 -> 3 -> 3 으로 사이클을 찾았지만 1 -> 3 -> 3 에서 찾았던 사이클)

 

처음에는 DFS를 한 번 돌고나서 check[]를 초기화하려고 했다. 즉, 모든 노드를 시작점으로 하는 DFS를 한 번 씩 수행하는 것이다.

 

모든 DFS마다 next node == start node인 경우가 나오면 사이클에 해당 DFS의 모든 노드들을 사이클에 포함시키는 것이다.

 

하지만 이 방법은 n제한 때문에 시간초과가 난다.

 

DFS의 시간복잡도는 O(V + E) 이고 이 문제에서 N = V = E로 모두 10만이고, 결국 O(20만) 짜리를 10만번 반복하게 되어O(2 * 10^12)로 시간초과를 맞는다. 

 

 

 

결국 풀지 못하고 정답을 확인했다.

 

이번에도 해답은 check[]에 있었다. dp[]를 dp[][]로 확장하여 사용하는 것과 같은 이 용법에 빨리 익숙해져야 한다.

 

boolean[] check 로 노드의 탐색 여부만을 체크하는 것이 아닌 int[] check 를 사용해서 몇 번째 DFS인지까지 체크한다.

(0 = 탐색한 적 없음, 1 = 1번째 DFS에서 탐색, 2 = 2번째 DFS에서 탐색 ... )

 

여기까지 오면 "주의사항 2" 까지는 해결이 가능하지만 '주의사항 1'이 아직 남아있다.

전역변수 isCycle, cycleStartNode를 통해 "주의사항 1" 까지 해결했다.

 

next가 "이번" DFS에서 이미 방문한 노드라면 해당 노드가 사이클의 시작점이 된다. 

next를 cycleStartNode에 저장하고 재귀됐던 함수들을 하나씩 반환하면서 node == cycleStartNode가 될 때까지 사이클에 포함되는 노드들을 체크한 후 isCycle을 OFF 해주면 정확하게 사이클에 포함된 노드들만 체크할 수 있다.

 

DFS의 원래 시간복잡도인 O(V + E) 로 처리가 가능하다.