[BaekJoon] 백준 9466번 텀 프로젝트

 

[BaekJoon] 백준 9466번 텀 프로젝트

 

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

 

 

내코드

 

- dfs문제인데 done배열을 추가해줘야하는 점이 조금 달랐다.

- 정답률 24퍼센트의 약간 어려운 문제였다.

- 아직도 완벽하게 이해는 가지 않는다 나중에 다시보기

- 사이클이 형성될 경우 사이클에 포함된 노드들의 수를 더하고 전체 학생수에서 빼면 됨.

- (visited == true && done == false)이면 사이클이 있는것(이미 방문해서 visited == true이지만 사이클을 이룰 경우 재방문할 가능성이 있기 때문)

- 따라서 현재 노드부터 다시 현재 노드로 돌아오기 전까지 cnt++을 해주면서 사이클 내에 있는 학생수를 세줌.

- 순환 호출을 이용해서 품.

- 아래는 아이패드에 정리한 내용

 

백준 9466번 텀 프로젝트.pdf

2.51MB

 

#include <iostream>
#include <string>

using namespace std;

const int MAX = 100000 + 1;
int T, n, cnt = 0;
int want[MAX];
int visited[MAX];
int done[MAX];

void dfs(int cur) {
	visited[cur] = true;
	int next = want[cur];
	if (!visited[next])	dfs(next);
    //방문했지만 방문이 끝난 노드가 아니면 사이클
	else if (!done[next]) {
    	//팀원을 모두센다
		for (int i = next; i != cur; i = want[i]) cnt++;
		cnt++;//자기자신을 센다
	}
	done[cur] = true;//더이상 해당 노드 방문 안함
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> T;
	while (T--) {
		cin >> n;
		cnt = 0;
		for (int i = 1; i <= n; i++) {
			visited[i] = false;
			done[i] = false;
		}
		for (int i = 1; i <= n; i++) {
			cin >> want[i];
		}
		for (int i = 1; i <= n; i++) {
			if (!visited[i]) dfs(i);
		}
		cout << n - cnt << "\n";
	}
	return 0;
}

 

참고

https://jaimemin.tistory.com/674