[BOJ] 9466 텀 프로젝트

cycle의 개수를 세야하는 문제였다. 이전에도 알고리즘 조교하면서 구현을 제대로 못했었는데 이번에도 어렵게 코드를 이해했다. 

 

9466번: 텀 프로젝트

이전에 확인한 cycle 관련코드도 지금 다시 보니 어질어질하다.

frieden1946.tistory.com/334

 

 

 

#include <iostream>

#include <cstring> //memset

using namespace std;



const int MAX = 100000 + 1;



int N, cnt;

int want[MAX];

bool visited[MAX];

bool done[MAX]; //방문이 끝났는지 여부



void DFS(int nodeNum)

{
    //cout << nodeNum<<" , ";

    visited[nodeNum] = true;
    int next = want[nodeNum];
    if (!visited[next])
        DFS(next);
        //이미 방문했지만 방문이 끝난 노드가 아니라면 사이클
    else if (!done[next])
    {
        //팀원을 모두 센다
        for (int i = next; i != nodeNum; i = want[i])
            cnt++;
        cnt++; //자기 자신을 센다
    }
    done[nodeNum] = true; //더 이상 해당 노드를 방문할 일이 없다
}

int main(void)

{

    int T;
    cin >> T;
    for (int i = 0; i < T; i++)

    {
        memset(visited, false, sizeof(visited));

        memset(done, false, sizeof(done));

        cin >> N;
        for (int j = 1; j <= N; j++)

            cin >> want[j];

        cnt = 0;

        for (int j = 1; j <= N; j++){
            if (!visited[j]){
                DFS(j); //팀을 이루는 사람들을 센다
                //cout << endl;

            }


        }




        cout << N - cnt << endl;

    }

    return 0;

}

 

아직 내가 돌고 있는 그래프 내에서 끝나지 않았다면 done은 false로 표시되어 있다. 내가 돌고 있는 그래프에서 cycle이 있는지 모두 확인했다면 done은 재귀를 끝내면서 true로 바뀌게 된다. 그러면 이 그래프에 대해서는 다시 들어가지 않는다.

 

1) next, visit x

    dfs(next)

 

2) next, visit o, done x

   cycle이니까 개수 세라

 

이거 다 끝나면 done으로 다 바꿔라

 

백준 9466번 텀 프로젝트