백준 9466 : 텀 프로젝트

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

1. 접근

• 한 학생이 가리킨 다음 학생을 따라 진행해야 하므로 DFS가 적절하다
• 팀에 속한 학생들을 찾고, 전체 인원수에서 제외해준다
• 한 학생은 한 명만을 가리킬 수 있으므로, 일반 int 배열을 사용해준다
• 기존의 dfs에서 사용한 visited 함수는 그대로 유지한다
• 연결 요소 문제와는 달리, 사이클이 완성되어야 한다
• 사이클에 속하거나, 아예 속할 수 없어서 더이상 확인할 필요가 없는 정점은 done 배열에 체크해준다
• cstring.h -> memset 함수로 배열들을 초기화해준다

---

2. 추가 반례 (질문 게시판 참고)

1

7

2 3 4 2 6 7 5

정답 1

---

3. 나의 풀이

#include <iostream>
#include <cstring>
#define MAX 100001
using namespace std;

int graph[MAX];
bool visited[MAX];
bool done[MAX];
int ret;

void dfs(int x) {
	visited[x] = true;

	if (!visited[graph[x]]) {
		dfs(graph[x]); //다음 노드 실행
	}
	else { //이미 방문했다면 
		if (!done[graph[x]]) { //다음 노드가 끝나지 않았다면
			//cout << "사이클 "<<x<<" ";
			for (int i = graph[x]; i != x; i = graph[i]) { //자기 자신으로 돌아올 때까지 반복문
				//cout << i<<" ";
				ret++;
			}
			ret++;
			//cout << "\n";
		}
	}
	done[x] = true; //모든 확인이 끝났음
	//cout << x << " done 처리 \n";
}

int main() {

	int t;
	cin >> t;

	for (int j = 0; j < t; j++) {
		int n;

		cin >> n;
		ret = 0;
		memset(graph, 0, sizeof(graph));
		memset(visited, false, sizeof(visited));
		memset(done, false, sizeof(done));

		for (int i = 1; i <= n; i++) {
			cin >> graph[i];
		}

		for (int i = 1; i <= n; i++) {
			if (!visited[i]) { //기존의 dfs 실행처리
				dfs(i);
			}
		}

		cout << n - ret << "\n";
	}
}

https://sw-ko.tistory.com/87
참고

---

평가

★★★★☆

어찌저찌 풀 수는 있었지만 dfs를 거의 활용하지 않았었다..
path를 추적해서 사이클을 찾는 알고리즘을 짰는데, 많이 비효율적이었던 것 같다.
그래프 문제는 최대한 기존의 dfs를 유지해서 푸는 방법으로 고민해봐야할 것 같다.