[백준] Q9466 텀 프로젝트 Gold III

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

9466번: 텀 프로젝트

 

1. 문제 유형 및 이해

위상정렬 또는 DFS , 그래프 이론

 

강의를 신청한 학생들이 텀 프로젝트를 하기 위해 팀을 꾸민다.

팀원수에 제한은 없다.

프로젝트 팀을 구성하기 위해 학생들을 '같이 하고 싶은 학생'을 선택한다.

팀이 되기 위한 조건은 다음과 같다.

학생들이 (s1, s2 ... sr)이라 할 때 r=1이고 s1 -> s1일 때, 또는 $s_1$ -> $s_2$, $s_2$-> $s_3$ ... $s_r-1$이 $s_r$을 선택하고 $s_r$ -> $s_1$을 선택하는 경우에만 한팀이 될 수 있다.

즉, 그림으로 그려보자면 다음의 두 상황입니다.

학생들의 상태

1. A의 경우와 같이 (A) 이고 A -> A 인 경우 (자기가 자기를 가리키는 경우)

2. B~F 의 경우와 같이 (s1...sr)이고 서로 연결이 되어 있는 경우.

* G의 경우 그룹(B, C, D, E, F) 에 들어가지 못합니다.

  들어가게 되면 (B, C, D, E, F,G)에서 조건을 만족하지 못하게 되기 때문입니다.

 

'학생'이라는 개념을 빼고 그래프만 보게되면 우리가 구하고자 하는 것은, cycle을 이루지 않는 노드의 개수 입니다.

'cycle'을 이루는 그룹을 찾아내야 겠다고 생각하면서 그래프 문제이다 라고 생각했습니다.

 

2. 문제 접근 방법

1. Dijoint set

처음에는 '그룹'에 집중하고 Dijkstra에서 cycle을 체크하는 Disjoint set을 생각했습니다.

다만 어떤 노드에서 cycle이 발생했을 때 해당 그룹이 모두 cycle을 이루는 집합이 아니라는 것을 깨달았습니다.

'큰 덩어리' 개념에서는 맞을 수 있겠으나 문제를 해결하기에 좋은 방법은 아니라고 생각합니다.

만약, 문제가 A와 BCDEFG를 구분한다면 괜찮겠지요

 

2. 위상정렬

문제를 읽고 위상정렬이구나 라고 하기 보다는 문제를 읽은 후 따라가다보니 위상정렬의 알고리즘을 사용할 수도 있겠구나 라고 생각이 들었습니다.

같이하고 싶은 학생이 없다면 자신에게 들어오는 edge가 0개 있을 것이고, cycle을 이룬다면 cycle을 이루는 모든 학생은 한 명이상의 자신에게 들어오는 edge가 있을 것입니다.

' 이 문제의 경우 edge가 하나이기 때문에 가능하다고 생각합니다.' 

 

즉, 위상정렬을 수행하면서 indegree가 0이되는 노드들을 count하여 제외합니다.

 

int[] list  : 자신이 원하는 학생의 number을 가지고 있습니다.(문제에서 주어진 input)

int[] inDegree : 자신을 원하는 학생의 수 입니다.

/*
2022.01.20
문제번호 : Q9466
이름 및 난이도 : 텀 프로젝트 Gold III
문제이해 
-----------------
프로젝트 팀원 수 제한이 X
(모든 학생이 한팀도 가능)
팀을 구성하기 위해 함께하고 싶은 학생 선택(단 한명만 선택가능, 자기 자신도 선택 가능)

제한 조건 : 
 T 
 학생의 수 2 <= n <=100_000

접근 방법 :
   한 팀이 되는 방법
    - 혼자서 
    - 또는 어떠한 그룹이 cycle을 이룰 때. cycle을 이루는 것 끼리.
    cycle을 이루는 가 라는 문제이다.
    어떠한 cycle그룹을 완성해 내야한다.
    
    disjoint set 문제라고 생각했음.
    cycle check 여부 그로 인해 만들어지는 어떠한 하나의 그룹.(수가 제한이 없다)
     ?? 어떠한 그룹이 cycle이 될 때 그 그룹은 모두 cycle이 되는가?
     그건 아니라는 걸 깨달음. 방향성이 없다면 가능할 수 있겠다.

    팀이 되는 방법을 자세히 보면 모두가 서로 연결되어 있는 것. 근데 이 원하는 필요한 노드에 방향성이 있음.
    즉 순서에 따라 진행했을 때 inDegree[] != 0 이 아닌 것.
    inDegree[] =0 이라는 뜻이 같이 하고싶은 사람이 없다는 것.
    (어떠한 노드가 연결이 되어있을 때 cycle이 되려면 그 그룹의 inDegree[]는 항상 1이상이다)

    추상화?
    어떤 방향 그래프에서 각 노드들의 edge가 하나밖에 없을 때,
    cycle을 이루는 집합을 구하세요.
    cycle을 이루는 모습을 보았을 때? edge는 하나 뿐임.
    위상정렬이 떠오르겟죠.

    또는 DFS로 푸는 방법이 있을 수 있겟다. Cycle이니까 자신에서 출발해서 자신으로 돌아오는 길이 있는지 확인.

*/

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

public class Main {
    static int N;
    static int inDegree[];
    static BufferedReader br;
    static int[] list;

    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            input();
            int ans = solution();
            sb.append(ans).append('\n');
        }
        System.out.print(sb.toString());
    }

    public static void input() throws Exception {
        N = Integer.parseInt(br.readLine());
        inDegree = new int[N + 1];
        inDegree[0] = -1; // dummy
        list = new int[N + 1];

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

    public static int solution() {
        int cnt = 0;
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 1; i < N + 1; i++) {
            if (inDegree[i] == 0) {
                cnt++;
                queue.add(i);
            }
        }
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            int nxt = list[cur];
            inDegree[nxt]--;
            if (inDegree[nxt] == 0) {
                cnt++;
                queue.add(nxt);
            }

        }
        return cnt;
    }

 

3. DFS

그래프에서 cycle을 체크하기 위해 그래프 탐색을 해야하는데, 문제의 경우 주어진 edge를 계속 타고 들어갈 수 있는 dfs로도 cycle을 체크할 수 있을 것입니다.

dfs에서 cycle을 체크하기 위해서는 이미 방문한 노드를 다시 방문한다면 어떤 cycle이 만들어졌다고 할 수 있습니다.

그래프 탐색을 하면서 방문 여부를 확인하기 위한 visited 배열과

cycle 체크를 위해 이미 답인지 아닌지 체크하기 위한 isFinished배열을 사용합니다.

 

isFinished 배열을 사용하는 이유는 위의 그림에서 F에서 dfs를 수행했다고 생각해보자.

F -> B -> C-> D- >... -> E -> F 와 같은 순서로 수행이된다.

이후에 G가 수행된다고 생각해보자.

isFinished 배열이 없다면

G -> F 에서 visited배열을 보니 방문한적이 있어서 cycle이라 생각하고 cycle을 다시 체크하는 경우가 생긴다.

이러한 경우를 제외해주지 않으면 반복적으로 cycle을 계산하여 오답 뿐 아니라 시간초과가 난다.

조금 더 좋은 변수명으로 isFinished 대신 isAlreadyTeam 도 괜찮을 것 같다.

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

public class Main {
    static int N;
    static int[] list;
     static int cnt;
    static boolean[] visited;
    static boolean[] isFinished;
    public static void main(String[] args) throws Exception {
        anotherSolve();
    }

    public static void anotherSolve() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            N = Integer.parseInt(br.readLine());
            list = new int[N + 1];
            visited = new boolean[N + 1];
            isFinished = new boolean[N + 1];
            cnt = 0;

            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 1; i < N + 1; i++) {
                list[i] = Integer.parseInt(st.nextToken());
            }
            for (int i = 1; i < N + 1; i++)
                dfs(i);
            sb.append(N - cnt).append('\n');
        }
        System.out.print(sb.toString());
    }

    public static void dfs(int cur) {
        if (visited[cur])
            return;
        visited[cur] = true;

        int nxt = list[cur];
        if (!visited[nxt])
            dfs(nxt);
        else {
            // 일반적인 dfs를 하다가 방문된 노드를 만났다. 즉, cur -> nxt)~~~->(cur 인 상황 만나버렸다.
            // visited 확인시 방문한적이 있다면 여기서 Cycle을 이룬다. 어디서든
            // 1-> 3-> 3이면 2번째 3에서
            // 4 -> 6 -> 7 -> 4라면 마지막 4에서
            if (!isFinished[nxt]) { // 처음 cycle을 체크한다면 해당 cycle을 모두 체크해준다. nxt노드는 cycle의 일부분일 테니까.
                cnt++;
               while(nxt != cur){
                   cnt++;
                   nxt = list[nxt];
               }
            }
        }
       isFinished[cur] = true;
    }
}