백준 9466 텀 프로젝트(dfs with cycle graph)

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

9466번: 텀 프로젝트

#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]; //방문이 끝났는지 여부

int numCycle;

void DFS(int nodeNum)

{

        visited[nodeNum] = true;

        int next = want[nodeNum];

        if (!visited[next])

                DFS(next);

        //이미 방문했지만 방문이 끝난 노드가 아니라면 사이클

        else if (!done[next])

        {

                //팀원을 모두 센다
                int i = next;
                while (i != nodeNum)
                {
                        i = want[i];
                        cnt++;
                        numCycle++;
                }

                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 << N - cnt << endl;
        }
        cout << numCycle;

        return 0;
}

// 출처: https://jaimemin.tistory.com/674#comment12294050 [꾸준함]

솔직히 이런 cycle문제를 처음봐서 아예 감도 못잡았다. 또한, 실력이 부족해서 jaimemin님의 코드를 이해하기도 벅찼다..ㅠ

 

이 문제와 코드는 보고서만 이해하기는 힘들다. 직접 그 과정을 적어가면서 봐야 이해가 빠르다.

 

가장 어려웠던 부분은 바로 

 

//팀원을 모두 센다

                 for (int i = next; i != nodeNum; i = want[i])

                         cnt++;

                 cnt++; //자기 자신을 센다



출처: https://jaimemin.tistory.com/674#comment12294050 [꾸준함]

이 부분이었다. 이 for loop가 어떻게 작동하는지 이해조차 하지 못했다.

 

결국 수소문(?) 끝에 이 코드가 

int i = next;
                while (i != nodeNum)
                {
                        i = want[i];
                        cnt++;
                }

이 코드와 같다는 것을 알게 되었다. 

 

이 코드가 cycle에서 구성요소의 개수를 세는 코드라는 것을 반드시 기억해야겠다.