개요

백준 9466번: 텀 프로젝트

• 입력
  첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

• 출력
  각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

접근방식

1. finished[] 배열을 만들고 dfs로 푸는 데 다른 점은 dfs가 끝나는 부분에서 finished배열을 true로 바꿔줌으로 해당 노드를 방문했는지 안했는지를 체크한다.

2. 만약 방문한 노드가 visited가 true지만 finishted가 false라면 싸이클이 돌아가고 있는 것이다.
   방문한 노드가 visited=true에 finished=true라면 이미 탐색이 끝난 컴퍼넌트이다.

3. 방문한 노드가 visited=true, finished=false라면 해당 노드에서 자기 자신으로 돌아올때까지 사이클을 다시 돌아보면서 갯수를 세본다. (한 노드에서 한 노드로만 연결되므로 가능하다 )

//해당 노드를 방문 했지만
		else {
			//완결난 컴퍼넌트 아니라면 싸이클 이므로
			if (!finished[Nodes]) {
				//싸이클인 지점부터 자신까지 올때까지 cycleCNt증가시킴
				for (int tmp = Nodes; adj[tmp] != Nodes; tmp = adj[tmp])
					cycleCnt++;
				//자기 자신 지점도 포함해줌
				cycleCnt++;
				return;
			}
			//방문했고 완결났다면 return
			return;
		}

4. 마지막은 전체 노드갯수와 만들어진 싸이클 갯수를 빼면 나머지 학생들이 나온다.

코드

#include<iostream>
#include<vector>
using namespace std;

void solution(int students);

int cycleCnt=0;
vector<int> adj;
vector<int>visited;
vector<int>finished;

//초기화해주는 함수
void init(int students) {
	cycleCnt = 0;
	adj.clear();
	adj.push_back(-1);
	finished.resize(students+1);
	visited.resize(students+1);
	fill(finished.begin(), finished.end(),false);
	fill(visited.begin(),visited.end(),false);
}

void dfs(int Nodes) {
		//해당 노드를 방문 안했고
		if (!visited[Nodes]) {
			visited[Nodes] = true;
			//완결난 컴퍼넌트가 아니라면
			if (!finished[Nodes]) {
				dfs(adj[Nodes]);
			}
		}
		//해당 노드를 방문 했지만
		else {
			//완결난 컴퍼넌트 아니라면 싸이클 이므로
			if (!finished[Nodes]) {
				//싸이클인 지점부터 자신까지 올때까지 cycleCNt증가시킴
				for (int tmp = Nodes; adj[tmp] != Nodes; tmp = adj[tmp])
					cycleCnt++;
				//자기 자신 지점도 포함해줌
				cycleCnt++;
				return;
			}
			//방문했고 완결났다면 return
			return;
		}
		finished[Nodes] = true;
	}

void input() {
	int T, amountStudents = 0,studentsNum=0;
	cin >> T;
	for (int i = 0; i < T; i++) 
	{
		cin >> amountStudents;
		init(amountStudents);
		for (int j = 1; j <= amountStudents; j++) {
			cin >> studentsNum;
			adj.push_back(studentsNum);
		}
		solution(amountStudents);
	}
}

void solution(int students) {
	
	for (int i = 1; i <=students; i++) {
		if (!visited[i]) {
			dfs(i);
		}
	}
	cout << students -  cycleCnt<< '\n';
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	input();
}

문풀후생

for (int tmp = Nodes; adj[tmp] != Nodes; tmp = adj[tmp])
					cycleCnt++;
				//자기 자신 지점도 포함해줌
				cycleCnt++;
				return;
			}

생각도 못한 방법이다.
for문을 이런식으로 사용하는 걸 배웠다.
늘 int i=0~이런식으로 짰었는 데 새롭다