[BOJ 9466] 텀 프로젝트 (Java)

BOJ 9466 텀 프로젝트

난이도 : 골드 3

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

9466번: 텀 프로젝트

 

전략

사이클을 형성하지 않는 노드의 수를 구하면 된다.

 

dfs 등 그래프 탐색으로도 해결할 수 있지만 방문 처리하는게 귀찮아서 위상정렬로 풀었다.

 

사이클에 포함되는 노드는 위상정렬 중에 방문되지 않는다.

이렇게 사이클에 진입하려고 하면 해당 노드가 진입차수가 0이 될 수 없어서 방문되지 않는다.

 

따라서 위상정렬하면서 방문된 노드의 개수를 출력하도록 하였다.

 

시행착오

위상정렬을 사용하기로 한 이후에는 시행착오가 없었다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            int N = Integer.parseInt(br.readLine());
            String[] line = br.readLine().split(" ");
            Student[] students = new Student[N + 1];

            for (int i = 1; i <= N; i++)
                students[i] = new Student(i);

            for (int i = 0; i < N; i++) {
                int l = Integer.parseInt(line[i]);
                students[i + 1].link = students[l];
                students[l].inDegree++;
            }
            System.out.println(sizeOfAcycles(students));
        }
        br.close();
    }

    static int sizeOfAcycles(Student[] students) {
        int ret = 0;
        Queue<Student> queue = new LinkedList<>();
        for (int i = 1; i < students.length; i++)
            if (students[i].inDegree == 0)
                queue.add(students[i]);

        while (!queue.isEmpty()) {
            Student cur = queue.poll();
            ret++;

            if (--cur.link.inDegree == 0)
                queue.add(cur.link);
        }

        return ret;
    }

    static class Student {
        int num;
        Student link;
        int inDegree = 0;

        Student(int num) {
            this.num = num;
        }
    }
}

 

깨달은 점

다양한 알고리즘 공부를 하다보니 문제를 해결할 수 있는 대안들이 생겨서 좋은 것 같다.