[백준] 10451번 순열 사이클

문제

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

풀이과정

순열 그래프에서 순열 사이클의 개수를 구하는 프로그램을 만드는 문제이다.
문제를 보면 dfs를 활용하는 기본적인 문제로 볼 수 있으며, 이제는 기본적으로 dfs를 구현할 줄 알게 됐고 실행이 잘 안되면 생각하며 고쳐갈 수 있게 되었다.

문제는 dfs로 탐색을 하며 끊어지는 부분이 나오면 개수를 하나씩 추가하는 식으로 풀었다.

이차원 벡터와 chk[]를 int형으로 두고 풀었는데 굳이 이차원 벡터를 쓸 필요도 없을 것 같고 chk[]는 bool형으로 쓰는 게 더 가독성이 높을 것 같다. 다음에 dfs 문제를 풀 때는 bool형으로 써야겠다.

그리고 fiil() 함수를 통해 벡터를 다시 0으로 초기화 해주고 memset()을 이용해 chk[]도 초기화 해주었는데 벡터를 초기화 하는 것은 굳이 필요없는 것 같다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int T, N;
vector<int> a[1001];
int chk[1001];
int ans;

void dfs(int node)
{
    chk[node] = 1;
    //cout << node << " ";
    for (int i = 0; i < a[node].size(); i++)
    {
        int next = a[node][i];
        if (chk[next] != 1)
        {
            dfs(next);
        }
    }
}

int main()
{
    cin >> T;

    while (T--)
    {
        cin >> N;

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

        for (int i = 1; i <= N; i++)
        {
            if (chk[i] != 1)
            {
                dfs(i); ans++;
            }
        }

        cout << ans << "\n";

        for (int i = 1; i <= N; i++)
        {
            fill(a[i].begin(), a[i].end(), 0);
        }

        memset(chk, 0, sizeof(chk));

        ans = 0;

    }

    return 0;
}