9466. 텀 프로젝트

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

9466번: 텀 프로젝트

 

일단 처음 봤을 때 한 방향 간선 그래프인것도 그렇고, 사이클을 찾아야 되는 것도 그렇고

10451. 순열 사이클과 비슷해 보였다.

풀다보니 다른점은 순열사이클 문제는 말그대로 사이클의 갯수를 구하는 것이고,

이 문제는 그 사이클안의 원소가 몇개인지 구하는 것이다.

처음엔 이전에 푼것을 이용해 금방 풀수 있을 것 같았는데 의외로 사이클안의 원소의 수를 구하기가 어려웠다..

 

...

계속 붙잡고 고민해봤는데 생각보다 어려웠다..

이전에 푼 문제랑 비슷하면서도 다르다.

햇갈렸던 것이 자기자신을 선택한 학생이 있을 때 였다.

얘 때문에 팀을 이룬 총 학생수를 구하기가 어려웠다.

 

결국 솔루션에서 원리만 보고 다시 풀었다.

 

 

방법은 이렇다.

dfs를 돌면서 다음 정점(학생)으로 가면서 cnt의 수를 1씩 늘리며 정점마다 저장한다.

그리고 dfs 한번에 갈수있는(간선이 이어져있는) 정점들은 동일한 step으로 저장한다.

그러니까 cnt배열, step배열을 선언해서 각각의 idx를 학생번호로 생각해 cnt랑 step을 저장하는 것.

 

그렇게 dfs를 돌다가 만약 cnt가 0보다 큰 정점을 만나면 이미 방문한 정점인 것이다.

그런데 이때 이 정점의 step이 지금 싸이클의 step과 같으면 같은 step의 그룹이니까 

현재 cnt값에서 이 정점의 cnt값을 빼면 이 step 그룹에 인원수가 나온다.

 

나는 이 step이라는 배열을 만들 생각을 못했다. 

 

코드

import java.util.*;

public class Main {
    static int[] a;
    static int[] c;
    static int[] s;

    static int cnt, step, teamn;

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        while(t-- != 0) {
            int n = sc.nextInt();

            cnt = 0; step = 0; teamn = 0; // reset
            a = new int[100001];
            c = new int[100001];
            s = new int[100001];

            for (int i = 1; i <= n; i++) {
                a[i] = sc.nextInt();
            }


            for (int i = 1; i <= n; i++) {
                if (c[i] == 0) {
                    cnt = 0;
                    step++;
                    dfs(i);

                }
            }
            System.out.println(n - teamn);
        }
    }

    static boolean dfs(int x) {
        cnt++;
        if(c[x] > 0) {
            if(s[x] == step) teamn += cnt - c[x];
            return false;
        }

        c[x] = cnt;
        s[x] = step;

        int y = a[x];
        dfs(y);

        return true;
    }
}