백준 (DFS) 9466번 - 텀 프로젝트

9466 - 텀 프로젝트 https://www.acmicpc.net/problem/9466

기존의 흔히 사용하는 DFS는 2차원 배열에서 값을 찾는 것이지만,

해당 문제는 1차원 배열에서 문제를 찾는 방식임.

1. 이미 방문한 곳은 방문하지 않도록 하기 위해서 visit1을 선언했다.

그냥 한번이라도 들리게 된다면 visit1의 값을 1로 변경했다.

그렇기 때문에 visit1의 값이 0일때만 깊이를 파고들도록 한다.

2. 순회의 끝을 찾기 위해서 visit2를 사용했다.

깊이를 들어갈 때마다 visit2의 값을 1로 변경했다.

그러다가 다음에 나올 visit2의 값이 만약에 0이라면 순회의 끝에 도달했다고 볼 수 있다.

그렇기 때문에 사이클을 돌려서 얼마만큼의 깊이까지 들어갔는지 체크를 하도록 한다.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int map[100001];
int visit1[100001]; //map에서 한번이라도 체크되었는지 확인.
int visit2[100001]; //순회의 끝을 찾기 위함.

int total, visit_count=0;

void dfs(int i)
{
	int a;
	int next = map[i];
	visit1[i] = 1;

	//printf("visit1[%d] : %d,             visit_count: %d\n", i, map[i], visit_count);

	if(visit1[next] == 0)
	{
		dfs(next);
	}
	else
	{
		if(visit2[next] == 0)
		{
			for(a=next; a!=i; a=map[a])
			{
				visit_count++;
				//printf("i : %d, a: %d, map[%d] : %d, visit_count : %d\n", i, a, a, map[a], visit_count);
			}
			visit_count++;
		}
	}
	visit2[i] = 1;
}

int main(void)
{
	int i, total_count = 0, non_visit_count =0, n;

	scanf("%d", &total);
	fflush(stdin);


	while(total_count++ <total)
	{
		memset(map, 0, sizeof(map));
		memset(visit1, 0, sizeof(visit1));
		memset(visit2, 0, sizeof(visit2));

		scanf("%d", &n);
		for(i=1; i<=n; i++)
		{
			scanf("%d", &map[i]);
		}
		fflush(stdin);

		visit_count = 0;
		for(i=1; i<=n; i++)
		{
			if(visit1[i] == 0)
			{
				dfs(i);
			}
		}

		printf("%d\n", n-visit_count);
	}


	return 0;
}