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

요약

DFS

하나의 테스트 케이스가 아래와 같이 주어졌다고 생각해보자.

5
2 3 4 5 2

2, 3, 4, 5 번이 하나의 팀으로 이루어질텐데,
재귀를 1번 부터 돌 때,
1 -> 2 -> 3 -> 4 -> 5 -> 2 (X) 여기서 2-> 3 -> 4 -> 5 -> 2 는 하나의 팀이 된다는 걸 한 번의 재귀에서 확인해줘야 한다.
이걸 1번 재귀가 끝나고, 다시 2번 재귀를 돌면서 확인하게 되면 시간 초과가 난다.

문제

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

풀이

check 라는 배열에
그룹을 만들 수 있으면 1, 만들 수 없는걸로 확인했다면 -1, 재귀의 시작점은 3, 재귀를 돌면서는 2로 기록했다.

• 재귀 함수에서 그룹원을 추가하며 1(이미 그룹을 만든 팀원 발견), -1(아미 팀을 만들 수 없는 팀원 발견)을 마주치면 현재 이루어진 그룹은 전원 팀 구성 불가능하므로 check : -1처리

• 3(재귀의 시작 팀원 발견)을 마주치면, 현재 그룹의 모든 팀원은 하나의 팀이 되므로 전부 check : 1처리

• 2(재귀를 돌면서 그룹에 추가된 팀원 중 한명)를 마주친 경우, start 라는 변수에 인덱스를 올려보며, 그룹에 포함되는 시작점을 찾았다. 그룹에 포함되기 전까지는 check : -1, 그룹에 포함된 이후부터는 check : 1 처리

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

int N;
int cnt;
vector<int>want;
int check[100001] = { 0, };
vector<int>group;

void init() {
    cin >> N;
    cnt = N;
    for (int i = 1; i <= N; i++) {
        int now;
        cin >> now;
        want.push_back(now);
        if (i == now) {
            check[now] = 1;
            cnt--;
        }
    }
}

void dfs(int now) {
    if (check[want[now]] == 1 || check[want[now]] == -1) {
        for (int i = 0; i < group.size(); i++) check[group[i]] = -1;
        return;
    }
    if (check[want[now]] == 3) {
        cnt -= group.size();
        for (int i = 0; i < group.size(); i++) check[group[i]] = 1;
        return;
    }
    if (check[want[now]] == 2) {
        int end = want[now];
        int start = 0;
        while (group[start] != end) {
            check[group[start]] = -1;
            start++;
        }
        for (int i = start; i < group.size(); i++) {
            check[group[i]] = 1;
            cnt--;
        }
        return;
    }
    check[want[now]] = 2;
    group.push_back(want[now]);
    dfs(want[now]);
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        memset(check, 0, sizeof(check));
        want.clear();
        want.push_back(0);
        init();
        for (int i = 1; i <= N; i++) {
            if (check[i] != 0) continue;
            if (check[want[i]] == 1) {
                check[i] = -1;
                continue;
            }
            group.clear();
            group.push_back(i);
            check[i] = 3;
            dfs(i);
        }
        cout << cnt << '\n';
    }

    return 0;
}