백준 9466 번 - 텀프로젝트(C++/DFS/Graph)

문제

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 

심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 

프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. 

(단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

 

학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., 

sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.

 

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

 

1 2 3 4 5 6 7

3 1 3 7 3 4 6

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

 

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

 

접근법

그래프 문제는 기초들만 풀어왔어서, 응용이 필요한 문제라 풀이를 이해하는데 시간이 오래걸렸다.

DFS로 끝을 확인 후(한 노드는 다른 한 노드만 가리킬 수 있으므로 (자신 포함)), 거기서 부터 순환을 이루나 체크했다. 

만약 순환을 이루지 않고 자기자신을 가리킨다면 자기자신을 가리킨 하나의 노드만 팀을 이루고, 순환을 이룬다면 모든 노드가 팀을 이룬다.

마지막에 cnt값을 전체값에서 제외해주면 끝난다.

        for (int i = next; i != here; i = adjacants[i])

 위 for문을 통해 순환을 시작했고 (for 문은 다음 노드가 visited==1일때만 실행되므로, 자기자신을 가리키거나, 순환이 완성됐을때만 실행)

완료가 되면 match를 1로 바꾸어 주어서 cnt되었던 것은 카운트 않도록 해준다.

다만 처음에 vector를 사용해서 구현했지만, 시간초과가 계속해서 떴다. 시간이 중요한 문제에서는 array를 사용해야 겠다.
시간초과된 코드는 아래 첨부한다. 기능은 같다.

코드

시간초과 버전(벡터(동적배열) 사용)

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
int match[100001] = { 0 };
int cnt = 0;
void DFS(int here, vector<int> adjacants, vector<int>& visited)
{

    visited[here] = 1;
    int next = adjacants[here];
    if (visited[next] == 0)
    {
        DFS(next, adjacants, visited);
    }
    else if (match[next] == 0) // visited == 1 && match == 0
    {
        cnt++;
        for (int i = next; i != here; i = adjacants[i]) 
            // 사이클이 맞나? 결국 자기자신으로 돌아오나 체크
        {
            cnt++;
        }
    }
    match[here] = 1;
}

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

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        memset(match, 0, sizeof(match));
        int M;
        cin >> M;

        vector<int> adjacants(M,0);
        for (int j = 0; j < M; j++)
        {
            int to;
            cin >> to;
            adjacants[j] = (to - 1);
        }
        vector<int> visited(M,0);
        cnt = 0;
        for (int j = 0; j < M; j++)
        {
            if (visited[j] == 0)
            {
                DFS(j, adjacants, visited);
            }
        }
        cout << M - cnt << "\n";
    }

}

통과 버전(정적배열 사용)

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
int match[100001] = { 0 };
int adjacants[100001] = { 0 };
int visited[100001] = { 0 };
int cnt = 0;
void DFS(int here)
{

    visited[here] = 1;
    int next = adjacants[here];
    if (visited[next] == 0)
    {
        DFS(next); 
    }
    else if (match[next] == 0) // visited == 1 && match == 0 즉, DFS로 순환 직전까지 간다.
    {
        cnt++; //자기자신 ++
        for (int i = next; i != here; i = adjacants[i]) 
            // 사이클이 맞나? 결국 자기자신으로 돌아오나 체크
        {
            cnt++; // 만약 끊겨있었다면 for문을 들어오지도 않으니 문제 X
        }
    }
    match[here] = 1;
}

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

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        memset(match, 0, sizeof(match));
        memset(adjacants, 0, sizeof(match));
        memset(visited, 0, sizeof(match));
        int M;
        cin >> M;

        for (int j = 0; j < M; j++)
        {
            int to;
            cin >> to;
            adjacants[j] = (to - 1);
        }
        cnt = 0;
        for (int j = 0; j < M; j++)
        {
            if (visited[j] == 0)
            {
                DFS(j);
            }
        }
        cout << M - cnt << "\n";
    }

}