[백준 9466] 텀프로젝트

이 문제는 DFS 알고리즘을 사용하여 사이클을 이루지 않는 사람의 수를 구하는 문제 입니다.

 

내 풀이

방향그래프에서의 사이클이 존재하는 지의 여부는 간선 구분을 통해 판정할 수 있습니다.

사이클이 존재한다는 것은 역방향 간선의 여부와 동치인데

그전에 역방향간선에 대해 간단하게 살펴보자면

 

그래프에서 Ti부터 DFS알고리즘을 돌리면 트리형태를 띠게됩니다. 그러한 트리를 DFS 스패닝 트리라고 합니다.

(Tm, Tj)의 간선은 스패닝트리의 자손에서 선조로 연결된 간선인 역방향 간선입니다.

 

그래서 사이클이 있는 그래프를 깊이우선탐색을 할 경우 무슨일이 벌어질지 생각해보면 쉽게 이해를 할 수 있습니다.

사이클에 포함된 정점 중 깊이 우선 탐색과정에서 처음만나는 정점을 u(Tj)라고 합시다.

dfs(u)는 u에서 갈 수 있는 정점들을 모두 방문한 후에야 종료할 겁니다. 따라서 깊이 우선탐색은 사이클에서 u이전에 있는 정점(Tm)을 dfs(u)가 종료하기 전에 방문하는데, 그러면 이 정점에서 u로 가는 정점은 항상 역방향 간선이 됩니다.

따라서 다시 정리하면 사이클에 포함여부를 알기 위해서는 역방향 간선을 찾고 그 역방향의 간선이 사이클의 끝과 시작 정점을 나타냅니다.

 

코드를 살펴봅시다.

역방향간선인지를 구하기 위해서는 (u,v)가 역방향 간선이라면 v가 u의 선조여야 합니다. 따라서 v는 u보다 일찍 발견이 되어야합니다.

발견순서 변수 counter를 이용하면 되는데 v가 u보다 일찍 발견이 된다고 하더라도 v가 u의 선조일수도 있고 아닐수도 있기때문에 구분하는 방법은 dfs(v)가 종료했는지를 확인 하는 것 입니다. dfs(v)가 아직 종료되지 않았다면 v는 u의 선조이니 (u,v)는 역방향 간선이 되는 거죠.

밑 코드의 discovered[]는 방문하였는지의 여부와 방문순서를 기록하기위한 배열입니다.

#include <iostream>
using namespace std;


int arr[100001];

//정점의 발견 순서
int discovered[100001];
int counter;

int finished[100001];
int n;
//사이클에 속하는 학생수
int circuitStdNum;

void dfs(int here) {
	
	//방문순서 저장
	discovered[here] = counter++;
	int there = arr[here];
	
	
	//기존 dfs와 동일하지만 문제조건상 "단 한 명만 선택할 수 있다"라는 점을 착안하여 인접리스트나배열이 아니다.
	//아직 방문하적 없다면 방문한다.
	if (discovered[there] == -1) {
		dfs(there);
	} //역방향간선 =은 학생이 본인을 택했을때도 고려 finished배열은 there정점이 dfs종료가 아직 안되었다는것을 표시
	else if (discovered[here] >= discovered[there] && finished[there] == 0)
	{
		//역방향간선의 here과 there의 방문순서를 빼고 1를 더하면 here과 there이 속한 사이클의 총 학생수를 구할수있다.
		int res =  discovered[here]-discovered[there] + 1;
		//이 결과를 circuitStdNum에 더해서 저장
		circuitStdNum += res;
		
	}

	finished[here] = 1;

	
}
int main() {
	cin.tie(0); ios::sync_with_stdio(0);
	
	int T;
	cin >> T;
	while (T--)
	{
		
		
		arr[0] = 0;
		circuitStdNum = 0;
		cin >> n;

		//초기화
		for (int i = 1; i <= n; i++)
		{
			cin >> arr[i];
			discovered[i] = -1;
			finished[i] = 0;
		}


		for (int i = 1; i <= n; i++)
		{
            //새로 방문하는 정점을 위해 방문하는 counter를 1로 초기화
			counter = 1;
            //아직 방문하지 않는 정점이라면 dfs시작
			if(discovered[i]==-1)
			dfs(i);
		}
		//사이클에 속하지않는 학생수를 구하는것이므로 전체 학생수에서 circuitStdNum을 빼야한다.
		cout << n - circuitStdNum << '\n';
		
	}
}

다른 풀이

  
else if (discovered[here] >= discovered[there] && finished[there] == 0)
	{
    	for (int i = there; i != here; i=arr[i]) circuitStdNum++;

                 circuitStdNum++; //자기 자신을 센다
		
	}

counter방문순서를 이용해 빼는것보다 counter는 방문순서 확인 용도로만 쓰고 이렇게 다시 for문도는것도 시간복잡도상 약간 느려질것같았지만 더 빨라집니다 20ms정도, 이유는 모르겠습니다;