백준 9446 텀 프로젝트 - C++, DFS

9466번: 텀 프로젝트

#include <iostream>
#include <cstring>
using namespace std;

int t, n, res;
int student[100001];
bool visit[100001];
bool isOnCycle[100001];

void DFS(int studentNum){
    visit[studentNum] = true;

    int nextStudent = student[studentNum];

    if(!visit[nextStudent])
        DFS(nextStudent);
    else if(!isOnCycle[nextStudent]){
        for(int i = nextStudent; i != studentNum; i = student[i])
            res++;
        res++;
    }

    isOnCycle[studentNum] = true;
}

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
            scanf("%d", &student[i]);

        res = 0;
        memset(visit, false, sizeof(visit));
        memset(isOnCycle, false, sizeof(isOnCycle));
        for(int i = 1; i <= n; i++){
            if(!visit[i])
                DFS(i);
        }
        printf("%d\n", n - res);
    }
}

---

 dp를 활용한 DFS를 구현했으며 '전체 학생 수 - 사이클에 잇는 학생 수'를 구하는게 핵심 아이디어 입니다.

 개인적인 생각으로는 추가적인 bool 배열 없이 함수의 인자로 넘겨서 진행을 하면 시간적으로나 공간적으로나 메모리를 아낄 수 있을 것 같은데 사이클 안에 들어있는 학생들을 어떻게 추적할지를 정하지 못해 위 방법대로 했습니다. 시간이 다른 사람ㄷ르의 풀이에 비해서 오래 걸리기 때문에 이후 개선할 여지가 있는 알고리즘입니다.