백준 9466 텀 프로젝트 (C++)

9466번: 텀 프로젝트

처음에는 단순히 모든 학생들이 DFS를 돌며 팀이 완성되면 DFS를 돌지 않는 방식으로 구상하여 문제를 풀어보았는데 시간 초과가 났었다. 아무리 나름대로 최적화를 해주었다해도 계속 시간 초과가 발생해서 결국 구글링을 해보았다. 알고보니 접근 방식부터 바꿨어야했다. 위와 같은 방식으로 접근하게 되면 결국 O(n^2) 의 시간 복잡도가 되어 시간 초과가 발생하게 된다. 아래 풀이는 방문하지 않은 학생들만 DFS를 했고 방문한 적이 있지만 사이클이 되지 않은 학생들을 카운트해주는 방식을 사용한다. 이러면 O(n)의 시간 복잡도를 가지게 되며 시간 초과가 발생하지 않게 된다. 문제 접근 방식을 다양하게 생각하도록 노력해야겠다.

#include <iostream>
#include <cstring>

using namespace std;

int T, n, res;
int A[100001];
bool visit[100001];
bool cycle[100001];

void dfs(int n) {
    visit[n] = true;
    int next = A[n];

    if (!visit[next]) {
        dfs(next);
    }
    else if (!cycle[next]) {
        for (int i = next; i != n; i = A[i]) {
            res--;
        }
        res--;
    }

    cycle[n] = true;
}

void solution() {
    res = n;

    for (int i = 1; i <= n; i++) {
        if (!visit[i]) {
            dfs(i);
        }
    }

    cout << res << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> T;

    while (T--) {
        memset(visit, false, sizeof(visit));
        memset(cycle, false, sizeof(cycle));

        cin >> n;

        for (int i = 1; i <= n; i++) {
            cin >> A[i];
        }

        solution();
    }

    return 0;
}