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

https://www.acmicpc.net/problem/9466

 

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

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

---

1.  아이디어

 

유방향 그래프에서 사이클에 속하지 않는 학생의 수를 구하는 문제가 된다. DFS 알고리즘과 위상 정렬을 활용하면 해결할 수 있다.

---

2. 문제풀이

 

DFS는 각 점에 대해 매번 탐색을 하면 중복되는 사이클이 있는 그래프에 반복 접근하게 되고 이 부분에서 시간초과가 발생하게 된다. 이를 방지하기 위해 임시 방문과 실제 방문 두 가지 방문 체크를 활용해서 임시 방문으로 사이클 여부를 파악 후 사이클이 존재하면 사이클의 크기를 구한 후 실제 방문 처리를 하는 방식으로 구현했다. 위상 정렬은 사이클이 존재하면 정렬할 수 없는 점을 활용해서 정렬된 노드의 개수가 사이클을 이루지 못한 학생의 수가 됨을 활용했다.

---

3. 코드

 

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

public class Main_DFS {

    private static int[] adj;
    private static boolean[] visited;  // 임시 방문 체크 배열
    private static boolean[] finished;  // 방문 체크 배열
    private static int sum;

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

        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            int N = Integer.parseInt(br.readLine());

            adj = new int[1 + N];
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                adj[i] = Integer.parseInt(st.nextToken());
            }

            visited = new boolean[1 + N];
            finished = new boolean[1 + N];
            sum = 0;
            for (int i = 1; i <= N; i++) {
                dfs(i);
            }

            sb.append(N - sum).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }

    private static void dfs(int node) {
        if (finished[node]) return;

        // 임시 방문한 노드를 다시 방문하면 사이클을 발견한 경우고 해당 위치는 사이클의 일부가 됨
        if (visited[node]) {
            cycle(node);
            return;
        }

        visited[node] = true;  // 현재 노드 임시 방문 체크
        dfs(adj[node]);
        finished[node] = true;  // 탐색 종료 후 방문 체크
    }

    // 방문 체크와 사이클 크기 계산
    private static void cycle(int node) {
        if (finished[node]) return;

        finished[node] = true;
        sum++;
        cycle(adj[node]);
    }

}

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

public class Main_TopologicalSort {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            int N = Integer.parseInt(br.readLine());

            int[] adj = new int[1 + N];
            int[] indegree = new int[1 + N];

            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                int token = Integer.parseInt(st.nextToken());

                adj[i] = token;
                indegree[token]++;
            }

            int sorted = topologicalSort(N, adj, indegree);
            sb.append(sorted).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }

    // 사이클을 이루지 못한 노드의 개수를 반환
    private static int topologicalSort(int N, int[] adj, int[] indegree) {
        int cnt = 0;

        Queue<Integer> q = new ArrayDeque<>();

        for (int i = 1; i <= N; i++) if (indegree[i] == 0) q.add(i);

        while (!q.isEmpty()) {
            int node = q.remove();
            cnt++;

            indegree[adj[node]]--;
            if (indegree[adj[node]] == 0) q.add(adj[node]);
        }

        return cnt;
    }

}

---

4. 후기

 

- DFS

- 위상 정렬