백준 9466번 텀 프로젝트

문제 링크입니다: https://www.acmicpc.net/problem/9466

DFS(Depth First Search) 알고리즘을 사용하여 사이클을 이루지 않는 사람의 수를 구하는 문제였습니다.

visited 배열은 기존에 풀었던 DFS 문제들에서도 사용하는 배열이였지만 done 배열은 처음 등장하는 배열입니다.

done 배열은 더 이상 이 노드를 방문하지 않을 것을 확신하는 경우에만 true가 됩니다.

즉, 이미 방문한 노드이지만(visited[노드] = true) 사이클을 이룰 경우 다시 방문할 가능성이 있기 때문에 (visited[노드] = true && !done[노드])라면 사이클을 이룹니다.

사이클이 형성될 경우 사이클에 포함된 노드들의 수를 더하고 전체 학생 수에서 빼면 답을 구할 수 있는 문제였습니다.

#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)

{

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

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~