[백준 9466] 텀 프로젝트 [C]

백준 - 9466

---

풀이

n명에 대해서 각각 dfs을 해 만들어진 팀의 학생 수 만큼 전체에서 빼면 된다.

중복을 방지하기 위해, 팀을 짜기 시작한 경우(visited[0])와 탐색이 끝난 경우(visited[1])로 확인을 해주었다.

 

이전에 만난적 없는 번호이면 짝을 찾아가고,

만난적 있는 짝일 때, 그 짝의 탐색이 끝나지 않은 경우라면 순환이 가능한 즉 팀이 만들어 질 수 있다.

순환점을 발견하기 전 까지 재 탐색을 하며 개수를 세주고, 마지막에 자기 자신을 세어 주면 된다.

---

소스코드

#include <stdio.h>
#include <stdbool.h>
#include <memory.h>
#define MAX 100001
bool visited[2][MAX];
int arr[MAX], N, cnt;

void dfs(int num, int depth){
    if (!depth){
        for (int i = 1; i <= N; i++)
            if (!visited[0][i])
                dfs(i, depth + 1);
    }
	
    visited[0][num] = true;
    int rink = arr[num];
    if (!visited[0][rink]) dfs(rink, depth);
    else if (!visited[1][rink]){
        int self = rink;
        while (self != num){
            self = arr[self];
            cnt++;
        }
        cnt++;
    }
    visited[1][num] = true;
}
int main(){
    int T;
    scanf("%d", &T);
    while (T--){
        memset(visited, 0, sizeof(visited));
        cnt = 0;
		
        scanf("%d", &N);
        for (int i = 1; i <= N; i++)
            scanf("%d", &arr[i]);
			
        dfs(1, 0);
        printf("%d\n", N - cnt);
    }
}

---

출처

9466번: 텀 프로젝트