백준 10451번 순열 사이클

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

간단한 DFS(Depth First Search) 알고리즘 문제였습니다.

flood fill 유형 문제에서 컴포넌트 개수 세듯이 하면 AC 받을 수 있습니다.

#include <iostream>

#include <cstring>

using namespace std;

 

const int MAX = 1000 + 1;

 

int N;

int arr[MAX];

bool visited[MAX];

 

void DFS(int node)

{

        visited[node] = true;

 

        if (!visited[arr[node]])

                 DFS(arr[node]);

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int T;

        cin >> T;

 

        for (int t = 0;t < T; t++)

        {

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

                 cin >> N;

 

                 for (int i = 1; i <= N; i++)

                         cin >> arr[i];

 

                 int cnt = 0;

                 for (int i = 1; i <= N; i++)

                         //컴포넌트 개수

                         if (!visited[i])

                         {

                                 DFS(i);

                                 cnt++;

                         }

                 cout << cnt << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

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