BOJ - 9466 텀 프로젝트

9466번 텀 프로젝트

텀 프로젝트를 진행하기 위해 팀을 선정해야 할 때 어느 팀에도 속하지 못한 학생의 수를 구하는 문제이다.

예를들어 1 2 3 번의 학생들이 팀을 짜야 하는데, 1번이 2번과 팀이 되길 원하고 2번은 3번과, 3번은 1번과 팀이 되길 원한다면 1,2,3번은 팀이 형성된 것이다. 반면 3번이 2번과 같은 팀이 되길 원한다면 2,3번은 팀이 된 것이고 1번은 팀에 속하지 못한 상황이 되는 것이다.

문제 해결을 위해 dfs알고리즘을 사용하였다.

문제 해결 과정은 다음과 같다.

1. dfs를 통해 깊이 들어갈 때 마다 depth를 +1 씩 해 준다.
2. 만약 해당 노드가 이미 방문한 적 있는 상태이면 해당 노드는 이미 다른 팀원을 지목한 상태이며 동시에 누군가에게 지목 당한 상태이므로 그 노트를 팀장으로 임명하고, 현재까지의 깊이를 final에 저장한다.
3. 갔던 길을 되돌아 오며 depht를 -1 씩 해 준다.
4. 만약 돌아오던 중 해당 노드가 팀장일 경우 final에 depth - 1을 저장해 준다.

예를들어 1(2) -> 2(4) -> 4(3) -> 3(2) 인 경우 마지막 노드가 원하는 팀원은 2번인데 2번은 이미 지목 하고, 당한 상태이므로 팀장이 된다.
(final = 4, depth = 4인 상태)

팀장이 2번이므로 돌아가는 과정에서 현재 노드가 2번이면 팀이 되지 못한 인원은 1번이 된다.
(final = 1인 상태)

반면 3번이 원하는 팀원이 5가 되고(3(5)) 5번은 이미 어느 팀에 속한 상태라면 1,2,3,4 번은 모두 팀이 되지 못한 인원이 된다.
(final = 4인 상태)

코드

#include <iostream>
#include <vector>

using namespace std;

int visited[100001];
vector<int>v[100001];
int cnt;
int n;
int team;
int depth;
int final;

void dfs(int s)
{
    if(visited[s] == 1)
    {
        team = s;
        final = depth;
        return;
    }

    final = 1;

    visited[s] = 1;
    depth++;

    dfs(v[s][0]);

    if(team == s)
    {
        final = depth-1;
    }
    depth--;

    return;
}

void sol()
{
    cin >> n;

    for(int i=1;i<=n;i++)
    {
        visited[i] = 0;
    }

    cnt = 0;

    for(int i=1;i<=n;i++)
    {
        int p;
        cin >> p;
        v[i].push_back(p);
    }

    for(int i=1;i<=n;i++)
    {
        team = -1;
        final = 0;
        dfs(i);
        cnt += final;
    }

    cout << cnt << "\n";

    return;
}

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

    int t;
    cin >> t;

    for(int i=0;i<t;i++)
    {
        sol();

        for(int i=1;i<=n;i++)
        {
            v[i].clear();
        }
    }
    return 0;
}

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