백준 10451:순열 사이클

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

백준 10451번 문제입니다. 이번 문제는 탐색을 활용하는 문제에요.

밑에는 제 코드입니다.

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define MAX 1001
 
int edge[MAX][MAX];
bool visited[MAX];
int N;
void dfs(int cur) {
    visited[cur] = true;
 
    for (int i = 1; i <= N; i++) {
        if (visited[i] || edge[cur][i]==0) continue;
        dfs(i);
    }
 
}
 
int main(void) {
    int T;
    scanf("%d", &T);
    for (int i = 0; i < T; i++) {
        int cnt=0,tmp;
        scanf("%d", &N);
        for (int k = 1; k <= N; k++) {
            scanf("%d", &tmp);
            edge[k][tmp] = 1;
        }
        for (int k = 1; k <= N; k++) {
            if (!visited[k]) { 
                cnt++;
                dfs(k); 
            }
        }
        printf("%d\n", cnt);
        memset(edge, 0, sizeof(edge));
        memset(visited, false, sizeof(visited));
    }
 
    return 0;
}

6~8:그래프배열과 방문체크 정점의 갯수 선언.

9~17:dfs함수입니다. cur에 방문했다고 체크하고 방문하지 않았고 cur->i로의 길이 있다면 dfs(i)로 이동해서 탐색합니다.

25~28:문제에서 주어진대로 k=1부터 k와 연결되는 tmp를 받아 그래프를 만듭니다.

29~34:탐색을 시작합니다. 방문하지 않았다면 갯수를 증가시키고 탐색시작.

35~37:갯수를 출력한뒤 memset함수로 그래프배열과 방문체크배열을 초기화합니다.