텀 프로젝트 9466

문제

접근 방법

DFS 문제인 것 같았다. 학생들이 팀이 될 수 있는 경우를 설명하는 것을 보면 알듯이 말이다.
그래서 숫자고르기와 유사하게 풀면 된다고 생각했다. 사이클이 생성 안 된 경우 증가하였지만, 결과는 시간초과였고 큐를 활용하여 이미 팀이 구성된 경우에는 체크를 하여 반복문에 안 들어오게 했음에도 안됐었다. 80퍼센트 정도까지 도달했을 때 그냥 다른 사람의 풀이를 보기로 결심했다.
다음 학생으로 DFS를 하며 한 바퀴를 돌았을 때 (사이클이 발견됐을 때) 이미 완료된 것이 아니면 (다른 곳에서 접근하는 경우를 차단) 한 바퀴를 돈 만큼 횟수를 증가시켜주고 전체 학생 수에서 빼주면 팀에 속하지 못한 학생들의 수를 구할 수 있다.

코드

#include <iostream>
#include <cstring>
using namespace std;
int arr[100001];
bool isVisted[100001], isDone[100001];
int ret;
void dfs(int cur)
{
    isVisted[cur] = true;
    int next = arr[cur];
    if (!isVisted[next])
    {
        dfs(next);
    }
    else if (!isDone[next])
    {
        for (int i = next; i != cur; i = arr[i])
            ++ret;
        ++ret;
    }
    isDone[cur] = true;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T;
    cin >> T;
    while (T--)
    {
        memset(isDone, false, sizeof(isDone));
        memset(isVisted, false, sizeof(isVisted));
        ret = 0;
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i)
            cin >> arr[i];
        for (int i = 1; i <= n; ++i)
            if (!isVisted[i])
                dfs(i);
        cout << n - ret << "\n";
    }
    return 0;
}

풀이

여러 사람 코드를 보니 다 비슷비슷했다.
풀이가 정해진 문제인 것 같다.
bool 배열 하나로 풀려 했는데 안 됐었다. 앞으로는 필요하면 고집부리지 말고 변수를 더 선언해야겠다.